sample frame from lecture video (L01)

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

Prof. Erik Demaine       TAs: Josh Brunner, Lily Chung, Jenny Diomidova

Lecture Videos and Classes [overview]

C01	Sep. 6	[+] Introduction: class overview; complexity theory crash course (P, EXP, R, NP, coNP, PSPACE, EXPTIME/SPACE, hard, complete); fun hardness proofs: Hamiltonicity in grid graphs, The Witness video game		[Erik's Notes]	[Slides]
	In our first class, I'll give an overview of the class and the format (which in future weeks involves watching video lectures); give a crash course in complexity theory and reductions; show a useful Hamiltonicity problem (in grid graphs) to reduce from; and prove hardness of a bunch of puzzle types in the video game The Witness, which are from a paper “Who Witnesses The Witness?” that grew out of the open problem session from a past version of this class. Then we'll all work in groups on related problems, some of which we know the answer to (pset-style) and some of which are unsolved problems in the field! (You can choose to work on any problems you like.) Please bring your laptop to class. Also, if you haven't already, please join the 65440-students mailing list, sign up for an account on Coauthor, and then fill out this signup form (even if you're just listening).
	L01	[+] OPTIONAL — Introduction: class overview; complexity theory crash course (P, EXP, R, NP, coNP, PSPACE, hard, complete); fun hardness proofs: Mario, Rush Hour.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This first lecture gives a brief overview of the class, gives a crash course in most of what we'll need from complexity theory (in under an hour!), and tease two fun hardness proofs: Super Mario Bros. is NP-complete, and Rush Hour (the sliding block puzzle, not the movie) is PSPACE-complete. (All terms will be defined in lecture. We won't have time to play these games in lecture, though, so feel free to get some practice in. :-)) Don't worry — 6.5440 has lots of serious and fun hardness proofs. Specifically, in the crash course we will define the complexity classes P, EXP(TIME), R, NP, coNP, PSPACE, and (less important) EXPSPACE, L, 2EXP, and 2EXPSPACE. We'll mention Savitch's Theorem (e.g., NPSPACE = PSPACE), the Time Hierarchy Theorem (e.g., P ≠ EXP ≠ 2EXP), and Space Hierarchy Theorem (L ≠ PSPACE ≠ EXPSPACE). Most importantly for this class, we'll define reductions, hardness, and completeness for these classes.
C02	Sep. 11 & 13	[+] 3-partition. Coauthor tips.		[Erik's Notes]
	This week, we'll work on a bunch of solved/open/coding problems where (we think) we can reduce from 3-Partition or Numerical 3-Dimensional Matching (for strong NP-hardness) or at least Partition or Subset Sum (for weak NP-hardness). Of course, it's difficult to predict, so some problems may not be amenable — in which case we might consider them again in future weeks too. Speaking of, feel free to work on last week's open problems too. There are some interesting remaining questions there based on the work so far, which I'll go over in class in our (probably daily) “progress report”. I'll also go over a few tips for using Coauthor, which are also on the class website. Finally, a reminder of the cadence of the class: Coauthor posts are due Sunday (11:59pm Eastern) Psets are due Monday at noon (PS1 already due, PS2 out now) Watching video lectures is due by the first corresponding in-person class Classes are Mondays & Wednesdays at 3-4:30+ and attendance is required (other than exceptions).
	L02	[+] 3-partition I. 2-partition vs. 3-partition; variations (Subset Sum, Numerical 3-dimensional matching, 3DM, X3C); weakly vs. strongly NP-hard; pseudopolynomial vs. polynomial. Multiprocessor scheduling, rectangle packing, edge-matching puzzles, jigsaw puzzles, polyform packing puzzles, packing squares into a square.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture introduces my favorite (and a generally lesser known) starting point for NP-hardness reductions, called 3-partition. This problem is particularly useful when you have a problem that involves adding up numbers, even when those numbers must be encoded in unary (a common feature of many puzzles). We'll discuss many variations of the problem: 2-partition: Partition integers into two sets of equal sum Subset Sum: Select integers to equal a target sum 3-partition: Partition n integers into n/3 triples of equal sum Numerical 3-dimensional matching: Integers are of three different types, and each triple must have all three types. 3-dimensional matching: A generalization to tripartite hypergraphs. Exact cover by 3-sets: A generalization to hypergraphs. 2-partition vs. 3-partition is an example of the weak vs. strong NP-hardness dichotomy, and on the algorithmic side, the pseudopolynomial vs. (weakly) polynomial dichotomy. We'll see weak and strong NP-hardness proofs, by reductions from 2-partition and 3-partition respectively, for two problems: multiprocessor scheduling packing rectangles into a rectangle Next we'll see a fun series of reductions between different puzzles, starting from 3-partition / rectangle packing to establish strong NP-hardness. edge-matching puzzles ("signed" like lizards, and "unsigned" like Eternity II) jigsaw puzzles polyomino packing puzzles (like Eternity) Finally, we'll see how to prove strong NP-hardness of packing squares into a square. This is a handy result that we'll use as the basis for another reduction next lecture.
	L03	[+] 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.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture includes 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] 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]
C03	Sep. 18 & 20	[+] SAT I. Polymorphism view of Schaefer's Dichotomy, nonbinary SAT/CSP dichotomy, planar dichotomy, symmetric dichotomy, S-in-kSAT		[Erik's Notes]
	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.
	L04	[+] SAT. SAT, Circuit SAT, CNF SAT, 3SAT, 3SAT-3, Monotone 3SAT, 2SAT, Max 2SAT, Horn SAT, Dual-Horn SAT, DNF SAT, 1-in-3SAT / exact-1 3SAT, NAE 3SAT / Not-All-Equal 3SAT, Schaefer's Dichotomy Theorem, 2-colorable perfect matching. Pushing blocks: Push-1, Push-∗, PushPush, PushPushPush, Push-F, Push-X, Sokoban. Conway's Phutball (Philosopher's Football), mate-in-1, Checkers.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	Satisfiability, particularly 3SAT and its many variations, is the prototype NP-complete problem, forming the starting point for almost all NP-complete problems. This class gives an overview of all the important variations, particularly the NP-complete ones, but also some close cousins which are polynomially solvable (so no good for NP-completeness!). Then we'll cover some examples of NP-hardness proofs based on 3SAT. First we'll look at pushing block puzzles popular in many video games (and with practical applications to warehouse motion planning). After introducing a variety of different such puzzles, such as Sokoban, we'll prove NP-hard Push-∗ and Push-1 and PushPush-1 (first in 3D, then in 2D). Finally, we'll cover Conway's Phutball (Philosopher's Football), where mate-in-1 is NP-hard, unlike Checkers where mate-in-1 is polynomial.
	L05	[+] Planar SAT. Planar 3SAT, planar monotone rectilinear 3SAT, planar positive 1-in-3SAT, planar NAE 3SAT (polynomial!), planar X3C, planar 3DM; planar vertex cover, planar (directed) Hamiltonian cycle, Shakashaka, flattening fixed-angle chains	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture introduces planar versions of 3SAT, in particular planar monotone rectilinear 3SAT and planar positive rectilinear 1-in-3SAT. But be careful: planar NAE 3SAT is polynomial. We will prove these versions of planar SAT are NP-hard. Then we'll reduce them to problems on planar graphs and in 2D geometry: Planar X3C (Exact 3-Set Cover) Planar 3DM (3-Dimensional Matching) Planar Vertex Cover Planar (Directed) Hamiltonian Cycle Shakashaka (another Nikoli puzzle) Flattening fixed-angle chains (at a high level)
C04	Sep. 25 & 27	[+] SAT II
	L06	[+] Linked Planar SAT. Linked, sided, monotone, planar 3SAT-3, interlinked; opening doors with 2 buttons, closing doors, NAND, crumblers, Mario, Pokémon, Zelda, (Push)Push-1(X), Push-1G, Pull?-1FG.		[Erik's Notes]	[Slides]	[Video]
	This lecture introduces Linked Planar 3SAT. Linked planar 3SAT is very useful for reductions for Mario-style games where an agent needs to traverse variable gadgets followed by clause gadgets without needing a crossover. In Linked Planar SAT, we have planar bipartite graph of variables and clauses, and also have cycle containing all of the variables followed by all of the clauses. We'll show this is NP-complete. We'll also introduce the door opening and door closing as an application of linked planar 3SAT, and use it to simply NP-hardness proofs of Mario, Zelda, Pokémon, and other games.
	L07	[+] Circuit SAT. Dual-rail logic vs. binary logic; Akari/Light Up, Minesweeper (consistency and inference); planar Circuit SAT; Candy Crush / Bejeweled	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	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: Akari / Light-Up (another Nikoli puzzle) Minesweeper consistency Minesweeper inference (which is actually coNP-complete) Candy Crush and Bejeweled (actually from 3SAT)
C05	Oct. 2 & 4	[+] Hamiltonicity and other Graph Problems.
	L08	[+] Hamiltonicity. Icosian game, planar directed max-degree-3, planar bipartite max-degree-3, max-degree-3 square grid graphs, triangle grid graphs, hex grid graphs, unit orthogonal segment intersection graphs. Euclidean degree-3 MST, Settlers of Catan mate-in-0, Slitherlink, Hashiwokakero. Milling, lawn mowing, 3D printing, minimum turns.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about Hamiltonicity (paths/cycles that visit every vertex exactly once). In particular, we'll see a very special and useful case that is NP-hard: grid graphs, defined by a set of points on a grid, with edges exactly when two points have unit distance. This version is hard for square, triangular, and hexagonal grids. We'll prove this and see how to reduce to other fun problems like optimally mowing your lawn, 3D printing, Settlers of Catan, and Nikoli puzzles Slitherlink and Hashiwokakero.
	L09	[+] Graph Problems. Vertex Cover: planar max-degree-3; exact vertex cover (polynomial), edge cover (polynomial), connected vertex cover, rectilinear Steiner tree. Vertex Coloring: planar max-degree-4 3-coloring, max-degree-3 3-coloring (polynomial). Graph Orientation: 1-in-3, 2-in-3, 0-or-3 vertices; packing trominoes. Graph Layout: Bandwidth, minimum linear arrangement, cutwidth, vertex separation, sum cut, edge bisection, vertex bisection; betweenness; bipartite crossing number, crossing number, Rubik's Cube.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is our last about straight-up NP-hardness. We've already seen the main techniques for such proofs, but there are a few other techniques that get used now and then. We will see three: Vertex cover, in particular planar vertex cover and planar connected vertex cover Vertex coloring, in particular planar max-degree-4 3-coloring Graph orientation, about assigning edge directions to satisfy vertex constraints. In particular, we will use these techniques to prove hardness of Rectilinear Steiner tree Pushing-block puzzles Push-1X and Push-1G (gravity) Crossing number A version of Rubik's Cube (just a rough sketch)
C06	Oct. 11, 16, 18	[+] Motion-Planning Games. Polynomial Hierarchy (Σk and Πk).		[Erik's Notes]	[Slides]
	In class, I'll give a brief overview of the Polynomial Hierarchy (classes Σk and Πk), which provide more of a continuum between NP and PSPACE.
	L10	[+] NP & PSPACE Video Games. Base PSPACE-complete problems: QSAT, Schaefer, planar Q3SAT, planar 1-in-3 Q3SAT. Viglietta metatheorems: location traversal, single-use paths, tokens, toll roads, pressure plates, buttons, doors. Applications to video games: Pac Man, FPSs (Doom, Quake, Heretic, Hexen), RPGs (Eye of the Beholder), adventure games (SCUMM), platformers (Prince of Persia, Sonic the Hedgehog, The Lost Vikings, Tomb Raider, Zelda II, Donkey Kong Country 1, 2, 3, Super Mario Bros., Lemmings)	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	Back to fun hardness of video games! We'll prove a bunch of “metatheorems”: video games with a few basic features are NP-hard or PSPACE-hard. Then we'll apply these metatheorems to prove NP-hardness of Boulderdash, Lode Runner, Zelda II, and Pac Man; and PSPACE-hardness of FPSs (e.g. Doom), RPGs (e.g. Eye of the Beholder), adventure games (e.g. SCUMM), Prince of Persia, Legend of Zelda: A Link to the Past, Donkey Kong Country 1, 2, and 3, and Lemmings.
	L11	[+] Motion-Planning Gadgets. Gadgets, states, locations, transitions, traversals, tunnels, buttons; system, connection graph, reachability, simulation. Door, self-closing door, symmetric self-closing door, universality, planarity. Deterministic reversible gadgets, hardness characterization, 2-state 2-tunnel gadgets. Checkable gadgets, Sokoban, Push-1F. I/O gadgets, 0-player, ARRIVAL. DAG vs. LDAG gadgets.		[Erik's Notes]	[Slides]	[Video]
	Gadgets gadgets gadgets! This lecture describes a growing general theory of "gadgets" in the context of "motion planning": an agent (e.g., Mario) traversing an environment with local state. We'll define a very general model of such gadgets, where each gadget consists of states, locations, and transitions between pairs of states and locations, and systems/networks of these gadgets connected in a graph structure. Then we'll describe some of the key results in this ongoing theory: Door framework: three gadgets that can each universally simulate all gadgets, even with a planar network (no crossings). Deterministic reversible gadgets: a complete characterization of which such gadgets are PSPACE-complete, with one gadget (Locking 2-Toggle) serving as a "basis" that every such gadget can simulate. Checkable gadgets framework: Lets you effectively ignore "broken" states in a gadget, as long as they are detectable (disable a particular traversal) and broken states stay broken. As an application, we'll see a solution to the long-standing open problem: Push-1F is PSPACE-complete. I/O gadgets and 0-player motion planning (fully deterministic system, still PSPACE-complete). DAG gadgets, and their relation to the door opening/closing gadgets we saw in Lecture 6.
C07	Oct. 23 & 25	[+] Constraint Logic.
	L12	[+] Nondeterministic Constraint Logic (NCL). Constraint graph, AND/SPLIT vertex, OR vertex, protected OR vertex, CHOICE vertex, red-blue conversion, wire terminators, crossovers, grid graphs. Constraint Graph Satisfaction is NP-complete, NCL is PSPACE-complete. Reconfiguration 3SAT, sliding-block puzzles, sliding tokens, Rush Hour, hinged dissection, Sokoban, Push-2F, rolling-block mazes, plank puzzles (River Crossing), dynamic map labeling, partial searchlight scheduling.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about Constraint Logic. We saw the basic model in Lecture 1 to prove Rush Hour is PSPACE-complete. Now we'll see the details of how Nondeterministic Constraint Logic (NCL) works, why it's PSPACE-complete, and how we can reduce to a very small gadget set: planar graphs with just AND and protected OR vertices. Then we'll apply NCL to prove PSPACE-completeness proofs for several different puzzles and problems: Reconfiguration 3SAT Sliding-block puzzles Sliding tokens Rush Hour Hinged dissection reconfiguration Sokoban Push-2F Rolling-block mazes Plank puzzles / River Crossing Dynamic map labeling Partial searchlight scheduling
	L13	[+] 0- and 2-player games. 0-player games: Conway's Game of Life is undecidable, Deterministic Constraint Logic (DCL) is PSPACE-complete. Bounded 2-player games are PSPACE-complete: impartial/partizan game/avoid/seek SAT, Kayles, Geography, Reversi/Othello, bounded 2-player Constraint Logic (Bounded 2CL).	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	We've proved hardness of a lot of puzzles, which can be viewed as 1-player games — the player represents the nondeterminism in move choices. This lecture is about games involving fewer or more players. Zero-player games are essentially simulations, like a regular computer. The prototypical example here is Conway's Game of Life, which is PSPACE-complete or undecidable depending on whether you bound the board. A more modern example is Deterministic Constraint Logic, a version of constraint logic where edge-reversal order is deterministically defined (but many edges reverse in parallel), which is still PSPACE-complete. In multiplayer games, we want to know whether a player (say, the first) has a winning strategy. In the worst case, all other players collude as a single entity, so the game reduces to two players. Thus we obtain 2-player games. We'll see many typical starting points for proving hardness of 2-player games, from QSAT itself to impartial/partizan game/seek/avoid SAT (from another amazing Schaefer paper). PSPACE-hard 2-player graph games include Kayles (essentially 2-player independent set), Geography (essentially 2-player longest path), Reversi/Othello, and bounded 2-player Constraint Logic (Bounded 2CL).
C08	Oct. 30 & Nov. 1	[+] Higher Games / Constraint Logic. 2-player motion planning through gadgets.		[Erik's Notes]
	We'll briefly describe known results about 2-player and team games in the general theory of gadgets.
	L14	[+] More Games. PSPACE-complete bounded 2-player games: Amazons, Konane, Cross Purposes. PSPACE-complete bounded 1-player stochastic games: SSAT. EXPTIME-complete unbounded 2-player games: formula games (G1, G2, G3, G4, G6), Peek, graph games (Ham, Block), Checkers, Chess, Go with Japanese ko rule, planar unbounded 2CL. APSPACE = EXPTIME. EXPSPACE-complete no-repeat unbounded 2-player games. 2EXPTIME-complete conditional no-repeat unbounded 2-player games. 2EXPTIME-complete private-information unbounded 2-player games. EXPSPACE-complete blind unbounded 2-player games.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	In this class, we'll see a few examples of real bounded games proved PSPACE-complete via Constraint Logic: Amazons, Konane, and Cross Purposes. Then we'll work our way up the game hierarchy: unbounded two-player games are EXPTIME-complete (including Chess, Checkers, and Japanese Go); with a “no repeat” rule they become EXPSPACE-complete (conjectured to include USA/Chinese Go); and with a “no recent repeat” rule they become 2EXPTIME-complete. Impartial information among the players similarly increases the complexity of unbounded two-player games, and furthermore distinguishes two-player games from team games with more than two players. I'll also mention some results that random (stochastic) players, such as rolling the dice, can be just as adversarial as regular (optimal) players — so-called “Games Against Nature”.
	L15	[+] Undecidability & P-completeness. Bounded team games with private information are NEXPTIME-complete: bounded Team Private Constraint Logic (TPCL). Unbounded team games with private information are undecidable: Team Computation Game, Team Formula Game, TPCL. P-completeness: NC, P-complete, machine simulation, Circuit Value Problem, SAM2CVP, bounded DCL, lexically first maximal independent set (greedy).	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture completes our coverage of games, explaining how it can be undecidable to determine winning strategies in games with bounded “resources”, when those games have private information and teams. Essentially, we can exploit the player's “heads” to store an arbitrarily large amount of information, and perform an arbitrarily complex computation in a long sequence of moves, even though the game's memory is itself small. In particular, the natural version of Constraint Logic is undecidable. (If the game has polynomially bounded length, however, the game is “only” NEXPTIME-complete.) This lecture also covers the notion of P-completeness (a frequent request from the survey), which is about the limits of parallel computation. P-complete problems are likely not in NC, meaning that they cannot be solved in polylogarithmic time even given a polynomial number of processors/gates. Constraint logic can be adapted here too, with bounded DCL. One detail here is that reductions need to be parallel algorithms, but this is pretty easy in gadget-based reductions.
C09	Nov. 6 & 8	[+] Beyond Decision Problems.
	L16	[+] #P and ASP. NP search problem, # problems, #P, parsimonious and c-monious reductions, SAT problems, Shakashaka, Hamiltonicity, Slitherlink, permanent, counting bipartite (perfect/maximal) matchings, counting minimal vertex covers, positive #2SAT. ASP (Another Solution Problem).	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about counting solutions, instead of just finding one. Given an NP problem and a notion of certificates for that problem, the counting version of the problem is to determine the number of valid certificates for a given instance. Analogous to NP, we get a class #P. In the world of Karp-style reductions, we get the notion of parsimonious (and “c-monious”, a term I made up) reductions that preserve the number of solutions (possibly with a uniform scale factor c). Many #P-hardness reductions are obtained this way. More generally, though, #P-hardness is defined relative to Cook-style multicall reductions. After reviewing some old proofs and whether they are parsimonious, we'll prove a bunch of problems #P-complete: Permanent of a matrix 0/1 permanent = counting perfect matchings in planar graphs #2SAT Hamiltonicity Nikoli puzzles Shakashaka and Slitherlink We'll also discuss the related notion of ASP (Another Solution Problem) and ASP-completeness. This area is motivated by many puzzles (such as Nikoli puzzles) which are supposed to be designed to have unique solutions. How can we tell whether the solution is unique, or equivalently, whether the puzzle has a second solution? Here we need our reductions to preserve solution uniqueness, a weaker condition than parsimony (but not c-mony).
	L17	[+] Inapproximability Intro. NP optimization problem, approximation, PTAS, APX, Log-APX, Poly-APX, PTAS-reduction, AP-reduction, strict-reduction, A-reduction, L-reduction, APX-hard. Max E3SAT-E5, Max 3SAT-3, independent set, vertex cover, dominating set.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture begins a series on inapproximability — proving the impossibility of approximation algorithms. I'll give a brief overview of most of the typical approximation factor upper and lower bounds in the world of graph algorithms. Then we'll introduce a bunch of general concepts, including new complexity classes (NPO, PTAS, APX, Log-APX, etc.) and stronger notions of reductions that preserve approximability (PTAS-, AP-, strict-, A-, and L-reductions). Finally, we'll prove APX-hardness for a bunch of APX-complete problems: Max 3SAT-3 Independent set Vertex cover Dominating set
C10	Nov. 13 & 15	[+] Inapproximability. L-reductions vs. gap-preserving reductions.		[Erik's Notes]
	We'll briefly compare L-reductions to gap-preserving reductions. Gap-preserving reductions are generally easier, because they let us compare to the ideal solution (instead of an unknown optimal solution). They also imply a stronger form of hardness to approximate: hardness for a specific gap, instead of hardness of solving all gaps simultaneously. The only downside to gap-preserving reductions is that they do not establish APX-hardness, which is useful from a complexity-class perspective. L-reductions do this, but are rather difficult to obtain because in particular they require preserving optimal solutions, not just ideal solutions.
	L18	[+] Inapproximability Examples. Max 2SAT, max NAE 3SAT, max cut, max/min CSP/ones characterization, max independent set, max 3DM-E2, max edge matching puzzles. APX-intermediate. Log-APX-complete: set cover, dominating set, token reconfiguration. Poly-APX-complete: independent set, clique. Exp-APX-complete: nonmetric Traveling salesman. NPO PB-complete: independent dominating set, longest induced path. NPO-complete: weighted SAT, 0-1 linear programming,	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture beings with a bunch more L-reductions to prove various problems APX-complete: Max 2SAT Max NAE 3SAT Max cut (max positive 1-in-2SAT) Max 3-dimensional matching Edge matching puzzles (maximize number of matches) More generally, we'll see a powerful characterization theorem of when minimizing or maximizing the number of satisfied clauses or number of true variables is approximable or inapproximable according to the structure of those clauses (in the spirit of Schaefer's Dichotomy Theorem). Next we'll also see some Log-APX-hardness, L-reducing from set cover to Dominating set Token reconfiguration puzzles I'll also briefly mention the higher end of the approximation spectrum: Poly-APX-complete: max independent set and clique Exp-APX-complete: nonmetric traveling salesman NPO PB-complete: longest induced path, longest path with forbidden pairs, minimum independent dominating set, shortest computation NPO-complete: max/min weighted SAT — find a satisfying assignment that maximizes/minimizes the sum of weights of true variables — and max/min 0-1 linear programming
	L19	[+] Gap Inapproximability. Gap problem, gap-producing and gap-preserving reductions, PCP theorem, max E3-X(N)OR-SAT, max E3SAT, Label Cover (Max-Rep and Min-Rep), directed Steiner forest, node-weighted Steiner tree, Unique Games Conjecture.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about gap problems: distinguishing between good and bad solutions, with a big gap in between those two notions. This perspective is particularly nice because we can turn NP-hardness of a decision problem into NP-hardness of approximation. It also often leads to tighter bounds on approximability. For example, we'll see a reduction that gives an optimal 7/8-inapproximability for Max E3SAT. A big tool here is the PCP (Probabilistically Checkable Proofs) theorem, which won a Gödel Prize in 2001. We'll see how gap problem hardness naturally leads to probabilistically checkable proofs and vice versa. Then we'll see the core PCP lower bound theorems, a problem called label cover (MinRep and MaxRep). Finally, we'll cover the Unique Games Conjecture, which (if true) leads to further improved inapproximability constants.
C11	Nov. 20 & 22	[+] Parameterized Complexity
	L20	[+] Parameterized Complexity I: W Hierarchy. Parameter, parameterized problem, XP, fixed-parameter tractable (FPT), Vertex Cover, EPTAS, parameterized reduction. W[1]: k-step nondeterministic Turing machine, Independent Set, clique in regular graphs, partial vertex cover, multicolored clique, shortest common supersequence, Flood-It on trees. W[2]: dominating set, set cover. W hierarchy: depth, weft, Weighted Circuit SAT, W[P], W[t], W[*], W[1], W[2], W[SAT].	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture begins our analysis of decision problems from a parameterized perspective, where we consider the dependence on an arbitrary parameter k in addition the problem size n. The algorithmic goal is to confine the exponential dependence to the parameter k instead of the problem size n. In this way, we get a deeper understanding of when the exponential time is reasonable (i.e. when k is small). More precisely, a problem is fixed-parameter tractable (FPT) if we can solve it in f(k) nO(1), for any function f(k), and constant O(1) independent of k. By contrast, a time bound of nf(k) is considered bad (but it has its own complexity class, XP). We'll introduce classes W[1] and W[2] conjectured to be distinct from FPT, by analogy to P ≠ NP. Then we'll see several problems that are complete in this classes, under a new reduction type called parameterized reduction. Specifically, k-step nondeterministic Turing machine is the canonical hard problem for W[1]. We'll prove that it's equivalent to Independent Set, and use that to prove W[1]-hardness of clique/independent set in regular graphs, partial vertex cover, and a useful base problem called multicolored independent set. We'll also see a reduction from the W[1]-hard problem shortest common supersequence to a puzzle game called Flood-It on trees. For W[2], the typical starting problems are Dominating Set and Set Cover. We'll show that these problems are at least as hard as W[1] by a reduction from multicolored independent set. Finally, we'll define the general W hierarchy in terms of the depth and weft of circuits and a problem called Weighted Circuit SAT (which could also be called Circuit k-Ones).
	L21	[+] Parameterized Complexity II: ETH & Planar. Exponential Time Hypothesis (ETH), strong ETH, 3-coloring, reduction size blowup, vertex cover, dominating set, Hamiltonicity, independent set, clique, planar 3SAT, planar graph problems, parameterized consequences of ETH, parameter blowup. Planar problems: Grid Tiling, list coloring, grid tiling with ≤, scattered set, independent set in unit-disk graphs.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about strong lower bounds on running time that are possible by assuming the Exponential Time Hypothesis: there is no 2o(n) algorithm to solve n-variable 3SAT. This conjecture is a stronger form of P ≠ NP, and it lets us keep track of “problem size blow-up”, something we've ignored before in our NP-hardness reductions. Many of the reductions we've seen, such as 3-coloring, vertex cover, dominating set, Hamiltonicity, and Independent Set/Clique have linear blow-up, so we get 2o(n) lower bounds. On the other hand, planar versions of these problems (except Clique) have quadratic blow up because of the crossover gadgets, so we get 2o(√n) lower bounds. In parameterized complexity, we get a particularly strong form of FPT ≠ W[1]: there is no f(k) no(k) algorithm for Clique/Independent Set, for any computable function f. In particular, there's no f(k) nO(1) (FPT) algorithm. By keeping track of the parameter blowup in our parameterized reductions, we can prove similar bounds for other problems, e.g. multicolored Clique/Independent Set, Dominating Set, Set Cover, and Partial Vertex Cover. Finally, we'll cover a useful base problem, called Grid Tiling, for proving W[1]-hardness of problems on planar graphs or in 2D. Specifically, we'll use Grid Tiling to prove Scattered Set is W[1]-hard in planar graphs, and that Independent Set is W[1]-hard in in unit-disk graphs. These results also imply that these problems have no EPTAS.
C12	Nov. 27 & 29	[+] Free-For-All
	This class, we don't have any assigned lecture videos (or new lecture material). We can return to solving any past problems we'd like!
C13	Dec. 4 & 6	[+] Free-For-All, wrap-up		Erik's Notes
	Alas, this week's class will be the last one in which we solve problems! In addition, I'll do a wrap-up summary of what we accomplished this semester, and we can discuss where to go from here.
C14	Dec. 11 & 13	[+] Student Presentations (room TBD)
	L22	[+] OPTIONAL — 3SUM & APSP. k-SUM upper and lower bounds, reductions. Distinct 3SUM, 3SUM′, GeomBase, 3 points on a line, point on 3 lines, Separator, Strips cover box, Triangles cover triangle, Hole in union, Triangle measure, Point covering, Visibility between segments, Visible triangle, Planar motion planning, 3D motion planning, fixed-angle chains. Nonquadratic lower bounds for triangle finding. Conjectured cubic graph problems: diameter, all-pairs shortest paths, negative triangle, radius, median.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is about hardness of problems that can be solved in polynomial time but where that polynomial seems to be substantially superlinear. Our focus will be on 3SUM (given n integers, do any 3 sum to zero?) which is conjectured to require roughly Θ(n2) time to solve. It has been the basis for many “3SUM-hardness” reductions, so if any of the problems can be solved in O(n2 − ε) time, then so can 3SUM. In class, we'll prove many problems 3SUM-hard, including a lot of computational geometry (where 3SUM originally comes from). We'll also talk about the generalization k-SUM, which has fairly strong lower bounds assuming ETH, and the conjectured-cubic graph problems all-pairs shortest paths and diameter.
	L23	[+] OPTIONAL — PPAD (guest lecture by Constantinos Daskalakis). Economic games, Nash equilibrium, Nash's Theorem, Brouwer's Fixed-Point Theorem, Sperner's Lemma, proofs and computational versions. Total search problems (TFNP), directed parity argument, End of the Line, PPAD, Arithmetic Circuit SAT.	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This lecture is the first of two guest lectures by Prof. Constantinos Daskalakis about the class PPAD which is intricately related to economic game theory (and a cool idea more generally). Costis is the expert in this area — his PhD thesis, for example, proved that finding Nash equilibria is PPAD-complete. Specifically, this lecture illustrates beautiful connections (reductions) between Nash's Theorem in economic game theory, Brouwer's Fixed-Point Theorem in topology, and Sperner's Lemma in graph theory. These problems are all PPAD-complete, meaning that they are the hardest search problems that have guaranteed solutions via “directed parity arguments” (formally, a problem called End of the Line). To prove PPAD-hardness (in the next lecture), we introduce an analog of Circuit SAT called Arithmetic Circuit SAT.
	L24	[+] OPTIONAL — PPAD Reductions (guest lecture by Constantinos Daskalakis). PPAD-completeness of Nash: graphical games, polymatrix games, 2-player games. PPA (Handshaking Lemma), PLS (sinks exist), PPP (pigeonhole principle).	[Scribe Notes] [src]	[Erik's Notes]	[Slides]	[Video]
	This class is Costis Daskalakis's second of two guest lectures. We'll focus on examples of PPAD-completeness reductions, from Arithmetic Circuit SAT to Nash equilibria in a few different settings—ultimately two-player games. Not covered but in the slides are other examples of PPAD-hardness reductions. Finally we'll hear about other classes related to PPAD, based on other styles of proofs of existence of solutions. PPA is based on the fact that, if a graph has a node of odd degree, then it must have another (which follows from the Handshaking Lemma). PLS is based on the fact that every directed acyclic graph has a sink node. PPP is based on the Pigeonhole Principle: any mapping from a set to a set of a smaller size has a collision.

Credits