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:

Plus we'll see a couple of weak NP-hardness reductions from 2-partition:

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]

Based on http://​dx.doi.org/​10.1016/​0743-7315(90)90019-L

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.