Final Project Guidelines

CS229cr: Spectral Graph Theory in Computer Science, Spring 2023

Overview

The final projects in the course are meant to give you the opportunity to further explore an aspect of the subject area that interests you, and give you the experience of formulating, carrying out, and presenting an interesting, short-term independent project. (We don't expect you to produce publishable results during the time you have this semester, but we do hope that some of the projects in the class can subsequently be developed into publishable research.)

Projects can be done individually or in pairs, with groups of three allowed for ambitious projects.

Many different types of projects are possible:

• Implement and experimentally evaluate algorithms that make use of spectral graph theory. 

• Seek new theoretical results on some aspect of spectral graph theory in CS or related topics.

• Connect the course material to some other area of interest to you (whether in CS or outside).

• Model some new problem that might not be captured by the current literature

• Synthesize and write an exposition of several papers or advanced readings in the  research literature (beyond those covered in detail in class)

• And more... be creative!

At the bottom of this document, we have included a list of pointers to help you as you search for topics and try to formulate your project.

Throughout the process, we encourage you to come to office hours and/or schedule individual meetings with the course staff to discuss your project ideas, in addition to the formal check-ins that we’ll organize after the project proposal.

Timeline

• Topic Ideas (Fri 3/3, revised Wed 3/22 Fri 3/24): As part of PS2 (due 3/3), submit about a paragraph of discussion about 1-3 ideas you have for potential project topics. For each topic, you should include the general kind of problem or use case that you'd like to address in your project and the general methodology (e.g. is it a theory project or an experimental project or...).   The point of these topic ideas is both to get you thinking about the project early on and to enable us to give you early feedback and suggestions, which we will provide by Wednesday 3/8.  We will only have covered a portion of the course material by then, so it is important to look ahead in the readings and search online to find topic areas that seem interesting to you.
  
  After that, we will set up a forum for you all to seek project partners with similar interests to yours, and your group should submit a revised, more detailed set of topic ideas, including an initial list of relevant papers, on March 22 24 (at the same time as PS3).
  
  

• Project Description (Fri 3/31): Submit a couple of pages giving a detailed description of what your final project will look like. You should be able to clearly state your research questions, briefly articulate how your project relates to what has been done in the past, describe the approach you are taking, give your timeline for completing various aspects of the project, and discuss your fallback plan in case the project doesn’t go as you hope.  In the month following your project proposal, we will arrange check-ins for each group to discuss their progress with and get suggestions from the course staff.
  
  

• Written Paper (draft due Mon 5/1, revision due Wed 5/10): Submit a paper (approx. 10 pages) describing your completed project. The paper should motivate your research questions and results, explain how the project fits into the context of previous work (with proper scholarly citations), justify the methodology, and present and interpret the results in a convincing manner. (Naturally, the form will differ depending on the type of project.)
  
  

• Presentation (exam period, Mon 5/8): Every group will give a presentation on their final project. Individual projects should present for 10 min, and group projects for 15-20 min.  The presentation should motivate the problem you worked on, describe your approach, and present and interpret the results.   We strongly recommend using a few prepared slides (else it is hard to convey much in a short talk), but avoid the temptation to pack in too much material (pick a few high-level points to convey) or fill the slides with too much text or formulas - try to convey as much as you can with pictures and diagrams.  (If you use Powerpoint, Alt-equals enables you to include nicely formatted LaTeX equations.)  As in your paper, be sure to give proper credit to previous work and clearly distinguish what you’ve done from what’s been done before.

Advice on writing and presenting your work

• “How to write a technical paper” by Michael Ernst.

• “How to give a technical presentation” by Michael Ernst.

• “How to give a great research talk” by Simon Peyton-Jones.

• “How to write a great research paper: Simon's seven easy steps.” by Stephanie Weirich.

• “How to give a good research talk.” by Stephanie Weirich.

• “How to Give  Bad Talk” by John Ousterhout, Tom Anderson, Dave Patterson (channeled by Mike Dahlin).

Pointers for formulating your project ideas

We recommend the following sources and the references therein as you start to develop the ideas for your project.  We will add more pointers as we think of them.  Be sure to explore beyond the small portion of the field that we have covered in the first few weeks of the course!

• Daniel A. Spielman.  Spectral and Algebraic Graph Theory.

• Luca Trevisan. Lecture Notes on Graph Partitioning, Expanders, and Spectral Methods.

• Lap Chi Lau. Eigenvalues and Polynomials.

• Nisheeth Vishnoi. Lx=b. 

• Shang-hua Teng.  Scalable Algorithms for Data and Network Analysis.

• The Algorithmic Spectral Graph Theory program at the Simons Institute for the Theory of Computing.  (See the program report and the many talk abstracts and videos.)

• Ravi Montenegro and Prasad Tetali.  Mathematical Aspects of Mixing Times in Markov Chains.

• Noga Alon. Spectral Techniques in Graph Algorithms.

• Salil Vadhan. Pseudorandomness. Especially the Notes and References of Chapter 4.

• Talks and proceedings of conferences in CS theory like STOC, FOCS, SODA, and ITCS, as well as in other fields of interest to you. (Search the titles and abstracts for words like “spectral”, “expanders”, “Laplacian”, “MCMC”, etc.)

• The topics in brackets listed in the course syllabus (most of which we may not cover in detail).