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] [Accessibility]

Lecture 3 Video     [previous] [next]

[+] 3-partition II: edge-unfolding polyhedra, snake cube puzzle, disk packing, Clickomania, Tetris, 1-planarity, GeoLoop/Ivan's Hinge.
2-partition: ruler folding, simple map folding.
This lecture includes 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]