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 6 Video     [previous] [next]

[+] Circuit SAT. Dual-rail logic vs. binary logic; Akari/Light Up, Minesweeper (consistency and inference); planar Circuit SAT; Candy Crush / Bejeweled [Scribe Notes] [src]

This lecture starts with a distinction between two key SAT reduction styles:

  • Dual-rail logic: variables + clauses (most proofs we've seen)
  • Binary logic: wires + splitters + clauses (crease pattern proof)
  • Circuit SAT: wires + splitters + universal gates
Then we will see a few proofs in the Circuit SAT style:

Download Video: 360p, 720p

Handwritten notes, page 1/6[previous page][next page][PDF]

Handwritten notes, page 1/6[previous page][next page][PDF]

Slides, page 1/28[previous page][next page][PDF]

http://​arxiv.org/​abs/​1203.1895

Slides, page 1/28[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.