6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

• 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]
• 1-planarity: Drawing a graph so that each edge crosses at most one other edge. [Grigoriev, Bodlaender 2007]
• GeoLoop / Ivan's Hinge (piano-hinged dissections) [Abel, Demaine, Demaine, Horiyama, Uehara 2014]

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]

This week is our first about SAT — in particular the NP-hard versions 3SAT, 1-in-3SAT, NAE 3SAT, planar 3SAT, and planar 1-in-3SAT. I'll kick us off with a modern “polymorphism” view of Schaefer's Dichotomy characterizing which versions of SAT are hard, along with extensions to nonbinary variables and restrictions to planar formulas.

Then we have a suite of new open, solved, and coding problems about variations of SAT and pushing blocks.