# CS 466/666 Final Project

For the final project, you will be asked to do **one** of the following:

- work on an open problem in algorithm design and present a survey about the problem and the outcomes of your investigations at the end of the term,
- present a survey of a topic of your choice (see some example topics below),
and
*analyze one of the main algorithms in that topic.*

The ideal project would be a problem/topic that you are excited about - this often brings one the most joy. If you need some guidance in picking a problem to present on, I will be happy to meet with you to hone into a problem of your liking.

The topics below are simply a suggestion. If you have another topic of your interest which is not covered here, I will be happy to try and work out with you a possible project on your topic of choice.

Students can work in groups of at most **2 people**.

## Timeline for the final project

- May 31st: decision on project groups due
- June 28th: project proposals due
- July 15th: revised proposals due
- August 7th: project reports due

## Requirements for the project proposal

In your project proposal, I would like a 1-page document (in LaTeX format - you can use this template) containing the following information:

- Title of your project
- Brief statement on the problem you will be working on
- Main algorithm that you will analyze (or main problem you will try to solve, or main lower bound you will present)
- Reference for the main algorithm
- Auxiliary references

## Requirements for the final report

A good final report will be one which can summarize in * ten pages*:

- a good introduction to the problem being studied (why is it relevant/previous results/current state of affairs),
- a summary of your approaches (if you decided to work on an open problem),
- progress made (if you manage to make any, even in particular special cases of the problem)
- analysis of one of the current best algorithms that solves your problem
- conclusion with open questions.

The limit to **10 pages** is simply because this is a constraint that even us researchers have when submitting a paper to a conference, so it should be doable to you as well, plus it is great practice.

Plus I intend to read all of them, and this limit will put my reading to somewhere between 300-600 pages.

Note: the references need to fit in the 10 pages.

### Template for final report

For the final project, we strongly recommend you to write it in LaTeX. A template that you can edit accordingly is given here.

## Grade rubric for final project

The final project will be worth 100 points, allocated as follows:

- 10 points: project proposal sent to me on time
- 10 points: successful revised project proposal agreed upon
- 80 points: project report

## Research-based projects

I highly encourage you all to try your hands at an open problem! It is an amazing and enriching experience, and you may end up solving it by the end of the class!

For those of you who want to use this opportunity to start working on some research problems (perhaps as a pre URA or an URF), here are people that you can check out their webpages/try to reach out to, or resources at your disposal, for you to look for suitable projects:

- Algorithms and Complexity faculty webpage
- Combinatorics and Optimization faculty webpage
- CrySP faculty webpage
- UW URA webpage

A good strategy to find interesting open problems is to look at a particular faculty’s advanced graduate course’s webpage and see the topics they are interested in and the open problems in the area that they would be interested in. You can use your final project to get a deeper understanding in such an area where your interests match.

## Sample Open Problems

- Is hyperbolic programming equivalent to semidefinite programming?
- Can one give rigorous guarantees on algorithms for metropolis light transport in graphics? Reference
- Can one efficiently count the number of perfect matchings in bipartite graphs of bounded treewidth? What about graphs with excluded minors? (see below for references on this problem)
- Open problems in sublinear time algorithms
- Polynomial time quantum algorithm for graph isomorphism problem? More generally, see Lomont’s survey of open problems about the hidden subgroup problem.

## Possible Survey Topics for Final Project

You can also find open problems here!

- Tropical Circuit Complexity connections between tropical circuits and Dynamic Programming
- Splay trees: alternative to splay trees
- Rank pairing heaps
- Zip Trees
- Power of Simple Tabulation Hashing
- Why simple hash functions work
- Monte Carlo approximation algorithms for enumeration problems
- MCMC approximation for Permanent of Nonnegative Matrices
- Expander Graphs and their Applications
- Survey on Pseudorandomness
- Sublinear Time Algorithms
- Randomized Numerical Linear Algebra
- Compressed Sensing
- Spectral Graph Theory
- Linear Programming rounding of NP-hard problems
- Extension Complexity of Polytopes
- Ellipsoid Algorithm
- Interior Point Methods
- Solving linear programming in matrix multiplication time
- Submodular Optimization
- Smoothed Analysis of Algorithms
- Semidefinite Programming and Sum of Squares decompositions: Sum of Squares solve everything?
- Semidefinite Extension Complexity (i.e. spectrahedral lifts) of convex sets
- Boaz’s Sum of Squares lecture notes with open questions at the end
- Fleming, Kothari, Pitassi Semialgebraic proof systems & algorithms survey
- Laplacian Solvers
- PCPs and their applications in hardness of approximation, or in the blockchain
- Hardness of approximation and Unique Games Conjecture
- Interactive Proofs
- 3SUM problem and 3SUM hardness of various problems
- Fine-grained complexity of algorithms: how (a lot of) hardness for hard problems translates into hardness for easy problems
- Lovasz Local Lemma and Moser-Tardos algorithmic version (and subsequent improvements)
- Distributed algorithms: Paxos for Byzantine Consensus
- Cache-oblivious algorithms
- Quantum Algorithms: Shor’s algorithm for factoring
- Deterministic parallel algorithms for (bipartite) matching Reference 1, Reference 2
- Counting number of perfect matchings of (bipartite) planar graphs in polynomial time
- Algorithms for Coding Theory (error correcting codes, list decoding, compression, locally decodable/correctable codes, codes that handle deletions, etc)
- Algorithms for Number Theory (last I checked we still could not factor integers quickly :) ) a reference on number theoretic algorithms by Shoup
- Algorithms in Cryptography: lecture notes by Pass and Shelat