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

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

[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]

Past Projects

For examples of research from past offerings of the class, see research from 6.892 2019 and research from 6.890 2014.

Project

The goal of a 6.5440 project is to complete work done during class into a finished (or nearly finished) form. The intent is to take the pieces of work done during in-class problem solving (or between classes) from posts on Coauthor to the next level of quality and polish, so that we can release them to the world.

Projects can take two forms:

Theory project: Write an original research paper, ideally in submittable form, as well as a presentation.
Coding project: Write useful software, ideally in releasable form, including documentation and demo.

(Solved problems are not candidates for projects. But if you have ideas for other types of projects, feel free to ask staff about suitability.)

Projects consist of three main components:

Write-up:
- For theory projects, this should be in the style of a research paper from the literature, with the goal of getting it published.
- For coding projects, this could consist of good documentation, including (a) how to use the software and (b) a design document detailing decisions made, challenges faced, etc.
Presentation: Aim to be like a presentation you would see at a conference.
- For theory projects, this should focus on the problem and results, and give a flavor of the proof.
- For coding projects, this should demo the software and explain why it's interesting.
Code: This should be a private repository in our GitHub organization.
- For theory projects, this should include the source code for the paper: LaTeX and all figures. In this case, you can use Overleaf if you prefer it over GitHub.

Scale

Both small and normal projects are encouraged. A "normal" project is at the scale of a typical final project in a graduate class (such as past versions of 6.5440). A "small" project is still interesting enough to be shared with the world but smaller in scope, and may be worth approximately half of one project portion of your grade (25% instead of 50%). Alternatively, a normal project but with equal contributions from an excessively large team may be treated like a small project (in the sense that the contribution of each member is small).

You can be involved in multiple projects, where two small projects are roughly equivalent to one normal project.

Collaboration

Like in-class problem solving, projects are strongly encouraged to be collaborative, ideally including everyone involved in the in-class work that led to the project.

If you work on a team, you will be required to post a short private Coauthor message (in the appropriate thread) summarizing everyone's contributions to the project. This will let us assign appropriate credit to students' overall project grades. In particular, if your contribution is small, you may receive a smaller weight than a full 50% of your grade.

Timing

Projects can be done at any time during the semester. If you obtain theory or coding results early in the semester, then we encourage you to finish the project while you still remember them well! We will try to grade projects in a timely fashion so you know where you stand with respect to the flexible grading scheme.

According to MIT policy, projects must be submitted before the last regularly scheduled lecture, which is Wednesday, December 13, 2023. But again, you can submit them earlier.

Procedure

Before you start a project, you should announce that you are doing so by adding a post with title "Project: <title>" to the relevant thread, requesting that everyone who wants to join should add themselves as a coauthor (and discuss with the others). Move this Project post to the top of the thread.
Also add the project tag to the Project post and the root post of the thread (so it's easy to see which problems have associated projects).
When you start a GitHub repository (make a private repo within our organization) or an Overleaf project for the code/write-up, link to that in the Project post (so everyone knows where to do work).
As you inevitably discover new results or mistakes while working on the project, be sure to keep the Coauthor thread up-to-date with new/edited posts.
When you've finished the project, attach two PDF files — the write-up and the presentation slides.
Also add the submit tag to the Project post, or a new child post (so we know to start grading).
If you worked in a team, you are also required to post a short private Coauthor message (in the appropriate thread) summarizing your own contributions to the project(s) you were involved in. This will let us assign appropriate project credit to the participants.

Presentation

Each project should be presented by all the major contributors (at least if they are taking the class for credit — if you don't want credit for the project, you are free to present or not as you desire). A project with k presenters will have 7 + k minutes for their presentation. So:

1-presenter projects can use 8 minutes
2-presenter projects can use 9 minutes
3-presenter projects can use 10 minutes
5-presenter projects can use 12 minutes

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.5440" in the subject.
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, HTML, and Google Slides links are all good options to send. I can install most any software you might need.
When your slides are final, you must also attach to your project post a PDF document with your slides, and then edit that PDF post to be coauthored by everyone who is presenting. (If you wish, you can also attach a PowerPoint file, or link to Google Slides or other cloud service, but PDF makes it easy to view the slides within Coauthor.)
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, but do not go over time. Practice your talk, both to measure and to optimize time spent.
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.