CS 860 Final Project
For the final project, you will be asked to work on an open problem at the interface of Algebraic Complexity and its connections to other areas (ideally an area of research that you are interested in). You will be required to present a survey about the topic/problem you chose and the outcomes of your investigations at the end of the term. Your survey must contain a technical component, be it the rigorous analysis of an algorithm or a proof of a lower bound for a computational task.
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.
Undergraduate students can do their final project in pairs, but it is not mandatory. I will leave it to you to coordinate the pairing for the final project.
Timeline for the final project
- February 10th: project teams due
- March 8th: project proposals due
- April TBD: project reports due
- April TBD: project presentations
Template for final project
For the final project, we strongly recommend you to write it in LaTeX. A template that you can edit accordingly is given here.
Possible Topics for Final Project
- Algorithms in Algebra and Algebraic Geometry Ideals, Varieties and Algorithms and Using Algebraic Geometry
- Computational Algebraic Geometry Hal Schenck’s book
- Hal Schenck’s Algebra and Topology for Data Analysis
- Hyperplane Arrangements Complex Arrangements
- Extension Complexity of Polytopes
- Semidefinite Extension Complexity (i.e. spectrahedral lifts) of convex sets
- Ellipsoid Algorithm for Geodesic Convex Problems
- Semidefinite Programming and Sum of Squares decompositions: Sum of Squares solve everything?
- Boaz’s Sum of Squares lecture notes with open questions at the end
- Fleming, Kothari, Pitassi Semialgebraic proof systems & algorithms survey
- Quantum Algorithms: Shor’s algorithm for factoring, Grover search
- Algebra in Coding Theory (error correcting codes, compression, locally decodable/correctable codes, codes that handle deletions, etc)
- Algebraic Approaches in Number Theory (last I checked we still could not factor integers quickly :) ) a reference on number theoretic algorithms by Shoup
- Algebraic Approaches in Cryptography: lecture notes by Pass and Shelat