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.

Research from 6.5440 2023

Here are the research publications resulting from 6.5440 in 2023 and beyond (as the group kept meeting in an open problem session), including research from the final projects in the class:
  1. “Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree” by Brian Liu, Nathan S. Sheffield, and Alek Westover, submitted

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:

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

Projects consist of three main components:

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

  1. 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.
  2. 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).
  3. 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).
  4. 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.
  5. When you've finished the project, attach two PDF files — the write-up and the presentation slides.
  6. Also add the submit tag to the Project post, or a new child post (so we know to start grading).
  7. 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: