6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2014)
Prof. Erik Demaine
TAs: Sarah Eisenstat, Jayson Lynch
[Home]
[Lectures]
[Problem Sets] [Project]
[Open Problems]
[Piazza]
[Accessibility]
Research from 6.890 2014
Here is the research publications resulting from 6.890 in 2014
and beyond (as the group kept meeting in an open problem session),
including research from the final projects in the class:
 “Visualizations of Block Pushing Hardness Reductions”
by Asa Oines, and associated
JavaScript application (click the Help button to get started).
An interactive visualization of the Push* NPhardness proof from Lecture 4.
 “Clickomania is Hard Even With Two Colors and Columns” by Aviv Adler, Erik D. Demaine, Adam Hesterberg, Quanquan Liu, and Mikhail Rudoy, published at MOVES 2015.
Solves an open problem from a paper in 2000 and from Lecture 3, characterizing the fewest colors and columns needed to prove NPhardness of the video game Clickomania (a.k.a. Same Game).
 “Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes, …” by Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Adam Hesterberg, Andrea Lincoln, Jayson Lynch, and Y. William Yu, published in Journal of Information Processing.
Generalizes the Tetris NPhardness proof from Lecture 3 to ktris for all k ≥ 2.
 “Simple Folding is Really Hard” by Hugo A. Akitaya, Erik D. Demaine, and Jason S. Ku, published in Journal of Information Processing.
Solves an open problem from a paper in 2000 and from Lecture 3, showing that simple folding of map crease patterns is strongly NPhard, not just weakly NPhard.
 “The Parameterized Complexity of Ricochet Robots” by Adam Hesterberg and Justin Kopinsky, published in Journal of Information Processing.
Proves that the PSPACEcomplete board game/puzzle Richochet Robots is W[SAT]hard with respect to the number of robots (so very unlikely fixedparameter tractable).
 “The Fewest Clues Problem” by Erik D. Demaine, Fermi Ma, Erik Waingarten, Ariel Schvartzman, and Scott Aaronson, published in Theoretical Computer Science.
Introduces a new type of problem where the goal is to find the fewest pieces of a solution that determine a unique solution, and proves various NPcomplete puzzles Σ_{2}complete in this setting, and some polynomialtime puzzles NPcomplete in this setting.
 “Multinational War is Hard” by Jonathan Weed, published in MOVES 2015.
Proves that the classic children's card game War is PSPACEhard when played with many players who have control over the order that they reinsert cards into their deck.
 “Computational Complexity of Arranging Music” by Erik D. Demaine and William S. Moses, published in MOVES 2015.
Proves NPhardness of arranging music under constraints, e.g., for playability on Rock Band.
 “Clickomania is Hard Even With Two Colors and Columns” by Aviv Adler, Erik D. Demaine, Adam Hesterberg, Quanquan Liu, and Mikhail Rudoy, published in MOVES 2015.
 “Mario Kart is Hard” by Jeffrey Bosboom, Erik D. Demaine, Adam Hesterberg, Jayson Lynch, and Erik Waingarten, published in JCDCGG 2015.
 “Dissection with the Fewest Pieces is Hard, Even to Approximate” by Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, and Anak Yodpinyanee, published in JCDCGG 2015.
 “Losing at Checkers is Hard” by Jeffrey Bosboom, Spencer Congero, Erik D. Demaine, Martin L. Demaine, and Jayson Lynch, published in MOVES 2017.
 “Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs” by Erik D. Demaine and Mikhail Rudoy, 2017.
Solves two open problems from a 2009 paper and from Lecture 8 about Hamiltonicity in grid graphs.
 “Computational Complexity of Generalized Push Fight” by Jeffrey Bosboom, Erik D. Demaine, and Mikhail Rudoy, published in FUN 2018.
 “Computational Complexity of Motion Planning of a Robot through Simple Gadgets” by Erik D. Demaine, Isaac Grosof, Jayson Lynch, and Mikhail Rudoy, published in FUN 2018.
 “Tatamibari is NPcomplete” by Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch, published in FUN 2020.
 “Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard” by Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch, published in ITCS 2020.
 “Path Puzzles: Discrete Tomography with a Path Constraint is Hard” by Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Roderick Kimball, and Justin Kopinsky, published in Graphs and Combinatorics, 2020.
Research from 6.890 in 2014 also led to parts of the following theses:
 “Hamiltonian Cycle and Related Problems: VertexBreaking, Grid Graphs, and Rubik's Cubes” by Mikhail Rudoy, 2017
 “Complexity of Minesweeper with Restricted Number Sets” by Ray Hua Wu, 2018
 “Characterizing Boolean Satisfiability Variants” by Ivan Tadeu Ferreira Antunes Filho, 2019
 ”Gadgets and Gizmos: A Formal Model of Simulation in the Gadget Framework for Motion Planning” by Dylan Hendrickson, 2019
 “A Framework for Proving the Computational Intractability of Motion Planning Problems” by Jayson Lynch, 2020
 “Exhaustive Search and Hardness Proofs for Games” by Jeffrey Bosboom, 2020
For more, see the list from 2019.
Project
The project is the most important component of the course. It can take several
forms:

Bring a theoretical contribution to the field (solve a problem, formulate an
interesting open problem or conjecture, etc.).

Survey a few papers on a related topic (not already wellcovered by the class).

Substantially improve the Wikipedia articles for several topics related to the class.

Implement/visualize one or more reductions. Your program should take in a description of an instance of a problem and output a corresponding instance of another problem. Some attention should be paid to the layout and aesthetics of the output.

Create an art project based on the ideas in the class. Your work should be both aesthetically compelling and technically grounded (though the latter need not be explicitly visible). You may use any medium you wish, but the challenge of working with that form will be taken into consideration.
You are encouraged to relate the final project to your research interests, and
you will not be limited to the topics discussed in class.
Project Proposals:
You must submit a project proposal by 11:59pm on October 29th. You should email
your proposal to 6890staff#at#csail.mit.edu. The proposal
should be about one page long (not more than two). It should discuss the
problem you chose in a clear and specific way.
We decide whether to approve your project's theme based on the proposal, so it
is imperative that you do some serious thinking about the project before
writing the proposal. Even though you should not change the topic of the
project after submitting a proposal, you may change the form of the project
(such as writing a survey if you fail in bringing a theoretical contribution).
Policies:

The project writeup may be done individually or in groups, though for groups we
expect proportionally larger projects. As always in
research, you are allowed and encouraged to consult with anybody, including the
teaching staff.

You must submit a paper on the day of our last class (December 9th, 2014), which should be
on the order of 10 pages. Send your paper via email to
6890staff#at#csail.mit.edu.

You are also required to do a presentation during the last few lectures.