6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

Prof. Erik Demaine     TAs: Sarah Eisenstat, Jayson Lynch

[Home] [Lectures] [Problem Sets] [Project] [Open Problems] [Piazza]

Lecture 3 Video     [previous] [next]

 [+] 3-partition II: edge-unfolding polyhedra, snake cube puzzle, disk packing, Clickomania, Tetris. 2-partition: ruler folding, simple map folding. [Scribe Notes] [src] Tomorrow's lecture will include a second (and final) bunch of strong NP-hardness reductions from 3-partition: Edge-unfolding polyhedra: A reduction from square packing (from L02). [Abel & Demaine 2011] Snake cube puzzle: Fold a chain of cubes with 90° bends at given locations into a larger cube. [Abel, Demaine, Demaine, Eisenstat, Lynch, Schardl 2013] Disk packing: Pack disks into a square (motivated by origami design). [Demaine, Fekete, Lang 2010] Clickomania: Delete monochromatic groups of size > 1 to erase everything. [Biedl, Demaine, Demaine, Fleischer, Jacobsen, Munro 2000] Tetris: Survive given piece sequence from given initial configuration. [Breukelaar, Demaine, Hohenberger, Hoogeboom, Kosters, Liben-Nowell 2004] possibly more surprise problems :-) Plus we'll see a couple of weak NP-hardness reductions from 2-partition: Ruler folding: Fold a carpenter's ruler to fit inside a 1D box. [Hopcroft, Joseph, Whitesides 1985] Simple map folding: Fold a square piece of paper along one line at a time to achieve specified creases. [Arkin,Bender, Demaine, Demaine, Mitchell, Sethia, Skiena 2000]
 No support for video detected. Install Flash or use an HTML5 browser. Download Video: 360p, 720p Handwritten notes, page 1/8 • [previous page] • [next page] • [PDF] Handwritten notes, page 1/8 • [previous page] • [next page] • [PDF] Slides, page 1/41 • [previous page] • [next page] • [PDF] Slides, page 1/41 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.