6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)

Prof. Erik Demaine       TAs: Jeffrey Bosboom, Jayson Lynch

Research from 6.892 2019

1. “Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players” by Jeffrey Bosboom, Charlotte Chen, Lily Chung, Spencer Compton, Michael Coulombe, Erik D. Demaine, Martin L. Demaine, Ivan Tadeu Ferreira Antunes Filho, Dylan Hendrickson, Adam Hesterberg, Calvin Hsu, William Hu, Oliver Korten, Zhezheng Luo, and Lillian Zhang, published in Journal of Information Processing, 2020.
2. “Tetris is NP-hard even with O(1) rows or columns” by Sualeh Asif, Michael Coulombe, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jayson Lynch, and Mihir Singhal, published in Journal of Information Processing, 2020.
3. “PSPACE-completeness of Pulling Blocks to Reach a Goal” by Joshua Ani, Sualeh Asif, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, Jayson Lynch, Sarah Scheffler, and Adam Suhl, published in Journal of Information Processing, 2020.
4. “Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets” by Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch, published in FUN 2020.
5. “1 × 1 Rush Hour with Fixed Blocks is PSPACE-complete” by Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff, published in FUN 2020.
6. “Arithmetic Expression Construction” by Leo Alcock, Sualeh Asif, Jeffrey Bosboom, Josh Brunner, Charlotte Chen, Erik D. Demaine, Rogers Epstein, Adam Hesterberg, Lior Hirschfeld, William Hu, Jayson Lynch, Sarah Scheffler, and Lillian Zhang, published in ISAAC 2020.
7. “Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard” by Josh Brunner, Erik D. Demaine, Dylan Hendrickson, and Julian Wellman, published in ISAAC 2020.
8. “Complexity of Solo Chess with Unlimited Moves” by Josh Brunner, Lily Chung, Michael Coulombe, Erik D. Demaine, Timothy Gomez, and Jayson Lynch, published in JCDCGGG 2022.
9. “This Game Is Not Going To Analyze Itself” by Aviv Adler, Joshua Ani, Lily Chung, Michael Coulombe, Erik D. Demaine, Yevhenii Diomidov and Quanquan Liu, published in JCDCGGG 2022.
10. “Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets” by Joshua Ani, Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch, published in WALCOM 2022.
11. “Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude” by Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch, published in FUN 2022.
12. “Hamiltonicity in Semi-Regular Tessellation Dual Graphs” by Divya Gopinath, Rohan Kodialam, Kevin Lu, Jayson Lynch, Santiago Ospina, arXiv:1909.13755, 2019.
13. “Traversability, Reconfiguration, and Reachability in the Gadget Framework” by Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, and Jayson Lynch, published in Algorithmica, 2023.
14. “The Legend of Zelda: The Complexity of Mechanics” by Jeffrey Bosboom, Josh Brunner, Michael Coulombe, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch, and Elle Najt, published in Thai Journal of Mathematics.
15. “Celeste is PSPACE-hard” by Lily Chung and Erik D. Demaine, published in Thai Journal of Mathematics.

1. “A Framework for Proving the Computational Intractability of Motion Planning Problems” by Jayson Lynch, 2020
2. “Exhaustive Search and Hardness Proofs for Games” by Jeffrey Bosboom, 2020
3. “Unsimulability, Universality, and Undecidability in the Gizmo Framework” by Joshua Ani, 2021
4. “Subway Shuffle, 1 × 1 Rush Hour, and Cooperative Chess Puzzles: Computational Complexity of Puzzles” by Josh Brunner, 2021
5. “Games meet Concurrency: Algorithms and Hardness” by Michael Coulombe, 2023

1. Puuush: Game engine implementing (Push(Push(Push)?)? and/or Pull(Pull(Pull)?)?)-F?X?G?-(1|2|…|∞) block games, for testing gadgets and generating figures/animations [deployed app]
2. NCL simulator: A webapp that lets you draw and simulate Nondeterministic Constraint Logic [deployed app]
3. Jigsaw reduction loop: 3-partition → edge matching → jigsaw puzzles → polyomino packing → edge matching [deployed app]

Project

The project is the most important component of the course. It can take several forms:

• Theoretical contribution to the field (tackle/solve a problem, formulate interesting open problems or conjectures, etc.).
• Survey a few papers on a related topic (not already well-covered by the class).
• Design a possible new lecture for a future edition of this class.
• Quick reference guide or visualization summarizing a large body of related results, e.g., SAT variations and which are easy/hard.
• Substantially improve the Wikipedia articles for several topics related to the class. Recommended only if you have existing experience editing Wikipedia. In this case, your project write-up and presentation should summarize the changes you made, why you made the decisions you did, and any challenges you ran into, in addition to linking to new articles and change diffs.
• 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.
• Implement/experiment with heuristics for NP-hard problems, e.g., those seen in class.
• Design a video/board/card game or puzzle, and analyze its complexity. Or design a game about reductions.
• Create artwork 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; the challenge of working with that format 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.

Deadlines

• Project proposals are due Tuesday, April 2, 2019 at noon, in place of a regular problem set, and should be submitted via Coauthor. See Problem Set 7 for details.
• The course staff will then give feedback on your proposal, including any tips and direction we can think of, and decide whether to approve your project's theme.
• If you decide to change your project direction substantially, it is required that you check in with the course staff to get feedback/approval on the new direction. You should not change the topic of the project, but you may change the form of the project (such as writing a survey if you fail to bring a theoretical contribution).
• Subsequent problem sets will mainly consist of project progress reports.
• By MIT policy, the project paper is due on the last regularly scheduled lecture of this class, Wednesday, May 15, 2019. Please turn it in by 7:00pm (start of class). No extensions are possible.
• The project presentation is due somewhat earlier depending on when it gets scheduled into a lecture slot; if your presentation is earlier, you are expected to have made less progress, but you should still give a clear description of the problem you are tackling and what you plan to do.

Collaboration

You are also welcome to collaborate with anyone outside the class, including your research supervisor (if you have one) and including the course staff. The only constraint for the class is that your own contribution should be substantial enough, both in terms of solving problems and writing it up. (To evaluate “substantial enough”, talk to the course staff.) In any case, collaborators should be clearly marked in the project proposal, paper, and presentation.

If you work on a team, you will be required to post a short private Coauthor message (in the appropriate thread) summarizing your own contributions to the project(s) you were involved in (when submitting the project). This will let us ensure that everyone makes substantial-enough contributions.

Multiple Projects

You are allowed to work on multiple projects, possibly with different teams. Just make sure that the total amount of work you do sums to at least one “person project unit”. We suggest having one as your main, or one or a small number to which you will make major contributions, along with any number of projects to which you will make minor contributions. We also require that you do some of the writing on at least one project paper, and participate in at least one of the project presentations.

In particular, we'd like projects tackling/solving open problems to match papers as much as possible. For example, instead of working on one project about two small papers, write two smaller projects. Conversely, instead of doing a project about your piece of a larger paper, be a part of a large project to write the entire paper. It's also fine to write up other people's results from open problem solving if they're OK with it (in particular, if they're not planning to do so for their class project) — help with writing is an important contribution to any paper!

Presentation

All presentations will during the usual class time on May 8 and 15, but will be in room 32-141. Some details/tips:

• Presentations are short, so be efficient in what you cover (and be sure to split the time roughly evenly between speakers). Focus on the problem you tackled, why it's interesting, and what results you came up with, and don't get bogged down in details. It's OK to go a little under time, in particular to leave a little time for questions, but do *not* go over time. Practice your talk, both to measure and to optimize time spent.
• All presentations will be off of Erik's (Windows) laptop, so be sure to email me your slides and any video files needed to play it, along with any software you want to demo (with instructions for how to get it running). Technically, we can display most files except Keynote (as it's MacOS only, but it can export PDF); PowerPoint, PDF, and Google Slides links are all good options to send. I can install most any software you might need.
• A draft of your presentation is due at noon on the day before your presentation (to make sure there are no technical issues); final files are due at noon on the day of your presentation. Do not show up with a USB key or laptop and expect to use the contents. (You can try emailing updated files after the deadline, and we'll do our best to incorporate, but no guarantees.)
• Email your presentation files to Erik with "6.892" in the subject.
• During the presentation, there will be a tablet showing you how much time you have left. It will make a bell sound when you have 2 minutes left, two bell sounds when you have 1 minute left, and three bell sounds when you must stop immediately.

Project Submission

To submit your final project, attach a PDF document to the relevant thread on Coauthor, and then edit that post to at-mention everyone involved in the project, and to add a link to the source files (LaTeX, figures, code, etc.). We require putting all source files into a repository on our MIT Github organization, or an Overleaf document with link sharing turned on, and including a link in your post. If you're unfamiliar with Github, here are some basic instructions:

• Create a new repository with title similar to your project (if you don't have one already), marked Private.
• If you're already using or know how to use Git, push your repository to the resulting remote.
• To just upload your files, go to https://github.mit.edu/6892-2019/YOUR-REPO-NAME/upload/master and drag your files in.