CS 278
Home
Project

CS 278: Final Projects

Project Logistics

  • 50% of your grade consists of your final project, done by yourself or with up to 2 others.

  • This will consist of a project proposal (1-2 pages), due October 1, 6pm PT

  • a mid-term project report (1-2 pages), due November 5, 6pm PT

  • a final project paper (at least 5 pages), and a final presentation in class. due December 10, 6pm PT

Project Categories

There are two types of projects you can do:

  • Survey of a complexity-related topic we haven't covered in class. See below for some suggestions, but any new topic is definitely welcome (consult the instructor if you feel the connection to complexity theory might be weak :) ).

  • Exploring an open direction related to complexity theory. This can involve either trying to make progress on an open problem or applying complexity-theoretic ideas to other fields. You are not required to solve any open problems to get a good grade. (You can always turn the project into a survey project if the open problems turn out to be too hard :) The point is to learn something new along the way.)

Suggested Project List

Again, you are not required to select from the list, but do consult the instructor to ensure the connection to complexity theory.

Survey Project

  • Project scope: Understand one cool paper related to complexity theory, for that you may also need to understand some important previous work of that paper. Below is a list of suggestions.

  • workload is estimated and may not be accurate

Arithmetic Complexity

Polynomial identity testing from (almost-equivalent) hardness assumption

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

Constant-Depth Arithmetic Circuits for Linear Algebra Problems

Circuit Complexity

Monotone Circuit Complexity of Matching

Fooling Constant-Depth Threshold Circuits

Proof Complexity and Bounded Arithmetic

Automating Resolution is NP-Hard

Reverse Mathematics of Complexity Lower Bounds

Meta-complexity

NP-Hardness of Learning Programs and Partial MCSP

Beating Brute Force for Compression Problems

Constant Depth Formula and Partial Function Versions of MCSP are Hard

SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

Derandomization

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization

When Connectivity Is Hard, Random Walks Are Easy With Non-Determinism

Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)

Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols

Simple Extractors for All Min-Entropies and a New Pseudorandom Generator

Near-Optimal Derandomization of Medium-Width Branching Programs

Derandomizing Logspace With a Small Shared Hard Drive

Time-space tradeoffs for element distinctness and set intersection via pseudorandomness

Hardness Magnification

Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds

Beyond Natural Proofs: Hardness Magnification and Locality

Quantum Complexity Theory

Unitary Complexity and the Uhlmann Transformation Problem

How to Construct Random Unitaries

Oracle Separation of BQP and PH

Open problem projects

  • Project scope: Pick one problem (or an open-ended direction) in complexity theory to think about.

  • Totally okay if you can't prove any new theorem, you can always either (1) write down the problem, discuss the state-of-the-art results, explain why it's diffcult to solve or (2) switch to a survey project on related topics.

Catalytic Space

Open problems related to catalytic space

Catalytic Communication

Machine Learning and Complexity Theory

Improve the decoder lower bound in complexity of Transformers

  • The paper proved some unconditional lower bounds against a (log log n)-layer decoder, which is a bit shallow. Can you improve the depth?

  • https://arxiv.org/abs/2412.02975

Improve the lower bound for Chain-of-Thought reasoning

  • CoT makes the transformer much more powerful in terms of expressive power. Prove some interesting new lower bound against “Transformer + CoT”

  • https://arxiv.org/abs/2502.02393

Develop an interesting complexity theory for autoregressive models

  • Interestingly, being able to solve an NC1-complete problem for an autoregressive model does not mean the autoregressive model can solve other (even very simple) NC1-complete problems (can you think about why?). Can we have a nice theory for the computational power of autoregressive models?

Circuit Complexity and Lower Bounds

Improve the AMEXP lower bound

  • The paper proves a maximum circuit lower bound for AMEXP with a sub-exponential amount of advice. Can you improve it?

  • lower the amount of advice

  • Make it hold for MAEXP with advice

  • or prove an algebraization barrier (see https:www.scottaaronson.compapersalg.pdf)

  • https://eccc.weizmann.ac.il/report/2024/182/

Derandomization

Many open questions in derandomization

Lots of open problems for unconditional PRGs

Meta-Mathematics

Many open problems in meta-mathematics