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 (psetstyle) 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 65440students 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 NPcomplete, and Rush Hour
(the sliding block puzzle,
not the movie)
is PSPACEcomplete.
(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  [+] 3partition. 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 3Partition or Numerical 3Dimensional Matching (for strong NPhardness) or at least Partition or Subset Sum (for weak NPhardness). 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:
 
L02  [+] 3partition I. 2partition vs. 3partition; variations (Subset Sum, Numerical 3dimensional matching, 3DM, X3C); weakly vs. strongly NPhard; pseudopolynomial vs. polynomial. Multiprocessor scheduling, rectangle packing, edgematching 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 NPhardness reductions, called 3partition.
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:
2partition vs. 3partition is an example of the weak vs. strong NPhardness dichotomy, and on the algorithmic side, the pseudopolynomial vs. (weakly) polynomial dichotomy. We'll see weak and strong NPhardness proofs, by reductions from 2partition and 3partition respectively, for two problems:
Next we'll see a fun series of reductions between different puzzles, starting from 3partition / rectangle packing to establish strong NPhardness.
Finally, we'll see how to prove strong NPhardness of packing squares into a square. This is a handy result that we'll use as the basis for another reduction next lecture.  
L03 
[+]
3partition II: edgeunfolding polyhedra, snake cube puzzle,
disk packing, Clickomania, Tetris, 1planarity, GeoLoop/Ivan's Hinge. 2partition: ruler folding, simple map folding. 
[Scribe Notes] [src]  [Erik's Notes]  [Slides]  [Video]  
This lecture includes a second (and final) bunch of
strong NPhardness reductions from 3partition:
Plus we'll see a couple of weak NPhardness reductions from 2partition:
 
C03  Sep. 18 & 20  [+] SAT I. Polymorphism view of Schaefer's Dichotomy, nonbinary SAT/CSP dichotomy, planar dichotomy, symmetric dichotomy, SinkSAT  [Erik's Notes]  
This week is our first about SAT — in particular the NPhard versions 3SAT, 1in3SAT, NAE 3SAT, planar 3SAT, and planar 1in3SAT. 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, 3SAT3, Monotone 3SAT, 2SAT, Max 2SAT, Horn SAT, DualHorn SAT, DNF SAT, 1in3SAT / exact1 3SAT, NAE 3SAT / NotAllEqual 3SAT, Schaefer's Dichotomy Theorem, 2colorable perfect matching. Pushing blocks: Push1, Push∗, PushPush, PushPushPush, PushF, PushX, Sokoban. Conway's Phutball (Philosopher's Football), matein1, Checkers.  [Scribe Notes] [src]  [Erik's Notes]  [Slides]  [Video]  
Satisfiability, particularly 3SAT and its many variations, is the prototype NPcomplete problem, forming the starting point for almost all NPcomplete problems. This class gives an overview of all the important variations, particularly the NPcomplete ones, but also some close cousins which are polynomially solvable (so no good for NPcompleteness!). Then we'll cover some examples of NPhardness 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 NPhard Push∗ and Push1 and PushPush1 (first in 3D, then in 2D). Finally, we'll cover Conway's Phutball (Philosopher's Football), where matein1 is NPhard, unlike Checkers where matein1 is polynomial.  
L05  [+] Planar SAT. Planar 3SAT, planar monotone rectilinear 3SAT, planar positive 1in3SAT, planar NAE 3SAT (polynomial!), planar X3C, planar 3DM; planar vertex cover, planar (directed) Hamiltonian cycle, Shakashaka, flattening fixedangle 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 1in3SAT. But be careful: planar NAE 3SAT is polynomial. We will prove these versions of planar SAT are NPhard. Then we'll reduce them to problems on planar graphs and in 2D geometry:
 
C04  Sep. 25 & 27  [+] SAT II  
 
L06  [+] Linked Planar SAT. Linked, sided, monotone, planar 3SAT3, interlinked; opening doors with 2 buttons, closing doors, NAND, crumblers, Mario, Pokémon, Zelda, (Push)Push1(X), Push1G, Pull?1FG.  [Erik's Notes]  [Slides]  [Video]  
This lecture introduces Linked Planar 3SAT. Linked planar 3SAT is very useful for reductions for Mariostyle 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 NPcomplete. We'll also introduce the door opening and door closing as an application of linked planar 3SAT, and use it to simply NPhardness proofs of Mario, Zelda, Pokémon, and other games.  
L07  [+] Circuit SAT. Dualrail 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:
 
C05  Oct. 2 & 4  [+] Hamiltonicity and other Graph Problems.  
 
L08  [+] Hamiltonicity. Icosian game, planar directed maxdegree3, planar bipartite maxdegree3, maxdegree3 square grid graphs, triangle grid graphs, hex grid graphs, unit orthogonal segment intersection graphs. Euclidean degree3 MST, Settlers of Catan matein0, 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 NPhard: 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 maxdegree3; exact vertex cover (polynomial), edge cover (polynomial), connected vertex cover, rectilinear Steiner tree. Vertex Coloring: planar maxdegree4 3coloring, maxdegree3 3coloring (polynomial). Graph Orientation: 1in3, 2in3, 0or3 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 straightup NPhardness. 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:
 
C06  Oct. 11, 16, 18  [+] MotionPlanning 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 PSPACEcomplete problems: QSAT, Schaefer, planar Q3SAT, planar 1in3 Q3SAT. Viglietta metatheorems: location traversal, singleuse 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 NPhard or PSPACEhard. Then we'll apply these metatheorems to prove NPhardness of Boulderdash, Lode Runner, Zelda II, and Pac Man; and PSPACEhardness 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  [+] MotionPlanning Gadgets. Gadgets, states, locations, transitions, traversals, tunnels, buttons; system, connection graph, reachability, simulation. Door, selfclosing door, symmetric selfclosing door, universality, planarity. Deterministic reversible gadgets, hardness characterization, 2state 2tunnel gadgets. Checkable gadgets, Sokoban, Push1F. I/O gadgets, 0player, 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:
 
C07  Oct. 23 & 25  [+] Constraint Logic.  
 
L12  [+] Nondeterministic Constraint Logic (NCL). Constraint graph, AND/SPLIT vertex, OR vertex, protected OR vertex, CHOICE vertex, redblue conversion, wire terminators, crossovers, grid graphs. Constraint Graph Satisfaction is NPcomplete, NCL is PSPACEcomplete. Reconfiguration 3SAT, slidingblock puzzles, sliding tokens, Rush Hour, hinged dissection, Sokoban, Push2F, rollingblock 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 PSPACEcomplete. Now we'll see the details of how Nondeterministic Constraint Logic (NCL) works, why it's PSPACEcomplete, 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 PSPACEcompleteness proofs for several different puzzles and problems:
 
L13  [+] 0 and 2player games. 0player games: Conway's Game of Life is undecidable, Deterministic Constraint Logic (DCL) is PSPACEcomplete. Bounded 2player games are PSPACEcomplete: impartial/partizan game/avoid/seek SAT, Kayles, Geography, Reversi/Othello, bounded 2player 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 1player games — the player represents the nondeterminism in move choices. This lecture is about games involving fewer or more players. Zeroplayer games are essentially simulations, like a regular computer. The prototypical example here is Conway's Game of Life, which is PSPACEcomplete or undecidable depending on whether you bound the board. A more modern example is Deterministic Constraint Logic, a version of constraint logic where edgereversal order is deterministically defined (but many edges reverse in parallel), which is still PSPACEcomplete. 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 2player games. We'll see many typical starting points for proving hardness of 2player games, from QSAT itself to impartial/partizan game/seek/avoid SAT (from another amazing Schaefer paper). PSPACEhard 2player graph games include Kayles (essentially 2player independent set), Geography (essentially 2player longest path), Reversi/Othello, and bounded 2player Constraint Logic (Bounded 2CL).  
C08  Oct. 30 & Nov. 1  [+] Higher Games / Constraint Logic. 2player motion planning through gadgets.  [Erik's Notes]  
We'll briefly describe known results about 2player and team games in the general theory of gadgets.  
L14  [+] More Games. PSPACEcomplete bounded 2player games: Amazons, Konane, Cross Purposes. PSPACEcomplete bounded 1player stochastic games: SSAT. EXPTIMEcomplete unbounded 2player games: formula games (G_{1}, G_{2}, G_{3}, G_{4}, G_{6}), Peek, graph games (Ham, Block), Checkers, Chess, Go with Japanese ko rule, planar unbounded 2CL. APSPACE = EXPTIME. EXPSPACEcomplete norepeat unbounded 2player games. 2EXPTIMEcomplete conditional norepeat unbounded 2player games. 2EXPTIMEcomplete privateinformation unbounded 2player games. EXPSPACEcomplete blind unbounded 2player games.  [Scribe Notes] [src]  [Erik's Notes]  [Slides]  [Video]  
In this class, we'll see a few examples of real bounded games proved PSPACEcomplete via Constraint Logic: Amazons, Konane, and Cross Purposes. Then we'll work our way up the game hierarchy: unbounded twoplayer games are EXPTIMEcomplete (including Chess, Checkers, and Japanese Go); with a “no repeat” rule they become EXPSPACEcomplete (conjectured to include USA/Chinese Go); and with a “no recent repeat” rule they become 2EXPTIMEcomplete. Impartial information among the players similarly increases the complexity of unbounded twoplayer games, and furthermore distinguishes twoplayer 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 — socalled “Games Against Nature”.  
L15  [+] Undecidability & Pcompleteness. Bounded team games with private information are NEXPTIMEcomplete: bounded Team Private Constraint Logic (TPCL). Unbounded team games with private information are undecidable: Team Computation Game, Team Formula Game, TPCL. Pcompleteness: NC, Pcomplete, 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” NEXPTIMEcomplete.) This lecture also covers the notion of Pcompleteness (a frequent request from the survey), which is about the limits of parallel computation. Pcomplete 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 gadgetbased reductions.  
C09  Nov. 6 & 8  [+] Beyond Decision Problems.  
 
L16  [+] #P and ASP. NP search problem, # problems, #P, parsimonious and cmonious 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 Karpstyle reductions, we get the notion of parsimonious (and “cmonious”, a term I made up) reductions that preserve the number of solutions (possibly with a uniform scale factor c). Many #Phardness reductions are obtained this way. More generally, though, #Phardness is defined relative to Cookstyle multicall reductions. After reviewing some old proofs and whether they are parsimonious, we'll prove a bunch of problems #Pcomplete:
We'll also discuss the related notion of ASP (Another Solution Problem) and ASPcompleteness. 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 cmony).  
L17  [+] Inapproximability Intro. NP optimization problem, approximation, PTAS, APX, LogAPX, PolyAPX, PTASreduction, APreduction, strictreduction, Areduction, Lreduction, APXhard. Max E3SATE5, Max 3SAT3, 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, LogAPX, etc.) and stronger notions of reductions that preserve approximability (PTAS, AP, strict, A, and Lreductions). Finally, we'll prove APXhardness for a bunch of APXcomplete problems:
 
C10  Nov. 13 & 15  [+] Inapproximability. Lreductions vs. gappreserving reductions.  [Erik's Notes]  
We'll briefly compare Lreductions to gappreserving reductions. Gappreserving 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 gappreserving reductions is that they do not establish APXhardness, which is useful from a complexityclass perspective. Lreductions 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 3DME2, max edge matching puzzles. APXintermediate. LogAPXcomplete: set cover, dominating set, token reconfiguration. PolyAPXcomplete: independent set, clique. ExpAPXcomplete: nonmetric Traveling salesman. NPO PBcomplete: independent dominating set, longest induced path. NPOcomplete: weighted SAT, 01 linear programming,  [Scribe Notes] [src]  [Erik's Notes]  [Slides]  [Video]  
This lecture beings with a bunch more Lreductions to prove various problems APXcomplete:
 
L19  [+] Gap Inapproximability. Gap problem, gapproducing and gappreserving reductions, PCP theorem, max E3X(N)ORSAT, max E3SAT, Label Cover (MaxRep and MinRep), directed Steiner forest, nodeweighted 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 NPhardness of a decision problem into NPhardness of approximation. It also often leads to tighter bounds on approximability. For example, we'll see a reduction that gives an optimal 7/8inapproximability 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, fixedparameter tractable (FPT), Vertex Cover, EPTAS, parameterized reduction. W[1]: kstep nondeterministic Turing machine, Independent Set, clique in regular graphs, partial vertex cover, multicolored clique, shortest common supersequence, FloodIt 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 fixedparameter tractable (FPT) if we can solve it in f(k) n^{O(1)}, for any function f(k), and constant O(1) independent of k. By contrast, a time bound of n^{f(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, kstep 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 FloodIt 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 kOnes).  
L21  [+] Parameterized Complexity II: ETH & Planar. Exponential Time Hypothesis (ETH), strong ETH, 3coloring, 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 unitdisk 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 2^{o(n}) algorithm to solve nvariable 3SAT. This conjecture is a stronger form of P ≠ NP, and it lets us keep track of “problem size blowup”, something we've ignored before in our NPhardness reductions. Many of the reductions we've seen, such as 3coloring, vertex cover, dominating set, Hamiltonicity, and Independent Set/Clique have linear blowup, so we get 2^{o(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 2^{o(√n) lower bounds. } In parameterized complexity, we get a particularly strong form of FPT ≠ W[1]: there is no f(k) n^{o(k)} algorithm for Clique/Independent Set, for any computable function f. In particular, there's no f(k) n^{O(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 unitdisk graphs. These results also imply that these problems have no EPTAS.  
C12  Nov. 27 & 29  [+] FreeForAll  
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  [+] FreeForAll, wrapup  Erik's Notes  
Alas, this week's class will be the last one in which we solve problems! In addition, I'll do a wrapup 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. kSUM 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, fixedangle chains. Nonquadratic lower bounds for triangle finding. Conjectured cubic graph problems: diameter, allpairs 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 Θ(n^{2}) time to solve. It has been the basis for many “3SUMhardness” reductions, so if any of the problems can be solved in O(n^{2 − ε}) time, then so can 3SUM. In class, we'll prove many problems 3SUMhard, including a lot of computational geometry (where 3SUM originally comes from). We'll also talk about the generalization kSUM, which has fairly strong lower bounds assuming ETH, and the conjecturedcubic graph problems allpairs shortest paths and diameter.  
L23  [+] OPTIONAL — PPAD (guest lecture by Constantinos Daskalakis). Economic games, Nash equilibrium, Nash's Theorem, Brouwer's FixedPoint 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 PPADcomplete. Specifically, this lecture illustrates beautiful connections (reductions) between Nash's Theorem in economic game theory, Brouwer's FixedPoint Theorem in topology, and Sperner's Lemma in graph theory. These problems are all PPADcomplete, 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 PPADhardness (in the next lecture), we introduce an analog of Circuit SAT called Arithmetic Circuit SAT.  
L24  [+] OPTIONAL — PPAD Reductions (guest lecture by Constantinos Daskalakis). PPADcompleteness of Nash: graphical games, polymatrix games, 2player 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 PPADcompleteness reductions, from Arithmetic Circuit SAT to Nash equilibria in a few different settings—ultimately twoplayer games. Not covered but in the slides are other examples of PPADhardness 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. 
Videography:  Martin Demaine  Equipment: Video shot with a Canon XA20 camera using a Sachtler Ace M Fluid Head with aluminum tripod. Lecture audio recorded using Countryman IsoMax E6 EarSet Microphone on camera using Sennheiser EW 112p G3 wireless microphone system, and audience audio recorded using Zoom H4n. See our guide to recording video lectures. 
Editor:  Erik Demaine  
Subtitles:  OCW 