# 18.405 Spring 2024 Project List

## Project Requirements

- The final project is done by yourself or with at most 2 others.
- This will consist of a project proposal (1-2 pages), periodic project progress updates (1-2 pages), a final project paper (at least 5 pages), and a final presentation in class. Due dates can be seen at the [course website](https://people.csail.mit.edu/rrw/18.405-2024/).
- At the dates they are due, the project proposal, progress updates, and final project paper should be emailed to the course instructor (Ryan) and the TAs (Ce, Tim, Zixuan).
- Your project could be a survey of a complexity-related topic we haven’t covered in class, or it consist of a new theorem (or set of new propositions) about some complexity-related topic.

## Claiming Projects

Guidelines for survey and research projects are listed below, but as soon as you have an idea for what paper(s) you’d like to base your project on:

- Check whether your project has been claimed and claim your project in the google sheet [here](https://docs.google.com/spreadsheets/d/1YEHYeDIzoX2XIYT_WYQDWVq19MTlJdEVjj3kiJM3ymo/edit?usp=sharing)
- Email the course TAs (please include all the TAs) with your name, the names of any others in your group (if you ware working with others), and the names of the papers you’re interested in working through. If you are interested in more collaborators for your project you can let us know that in the email.
- Please send this email as soon as you have a good sense of what papers you’d like to read for the project. In particular, it’s good to email and claim which paper(s) you’re interested before the actual project proposal deadline, to avoid overlapping too much with other students’ projects.

## Guidelines for Reading (Survey) Projects

- In general, you are allowed to pick any complexity-related topic (that is not covered in class) that interests you (but check with us first!).
- You are encouraged to study several interesting frontier papers on that topic, and compose them into a survey with a coherent story. Of course, if you find recent papers too hard to read (which is very possible), you can also pick some older and more reader-friendly papers.
- You are of course not required to prove all the things in the surveyed papers. You can just give the high-level ideas of the proofs, and/or omit technical things which in your opinion won’t help the reader to understand things better.
- Even if you are doing a survey, we are expecting something new and original from you. You should put your efforts into the survey so that the exposition there has **some advantage over the original papers** (in other words, your survey should make people **want to read your survey instead of the original papers**).
- Please remember that **copying is plagiarism, and you should not do it**. Ryan reads **LOTS** of papers, and is likely to tell if a section is copied from a paper you have read.

## Guidelines for Research Projects

- Since complexity theory is considered to be a hard subject, we recommend you to study many previous works on your research topic first so that if you end up with no new theorems, it can be smoothly changed to a reading project.
- Please don’t use a project which you are already working on as the course project. But you are encouraged to connect your research field to the course material, and start a project based on that.

## Project List

The project list below offers some suggestions on potential research or reading topics. It is absolutely OK if you want to pick another topic which is not listed below. But **make sure your topic is complexity-related** (remember, check with us to make sure it is related!).

## Circuit Lower Bounds

### The Algorithmic Methods Towards Circuit Lower Bounds
The algorithmic method connects non-trivial circuit analysis algorithms and circuit lower bounds. The following two works establish a connection between $2^{n−n^ε}$–time circuit analysis algorithms and lower bounds for non-deterministic quasi-polynomial time.

- [Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP](http://people.csail.mit.edu/rrw/easy-witness-nqp.pdf)
- [Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits](https://eccc.weizmann.ac.il/report/2019/031/)

The following paper shows how to extend the above methods in the case of average-case complexity (note: this is longer and more technical than prior work):

- [Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization](https://eccc.weizmann.ac.il/report/2020/010/)

In the following two works, the authors apply the algorithmic method to prove lower bounds against certain exact / approximation linear combinations of simple functions.

- [Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials](http://drops.dagstuhl.de/opus/volltexte/2018/8884/)
- [Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity](http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=10841)

For the case of symmetric circuits recent new lowerbounds have been proven:

- [Symmetric Exponential Time Requires Near-Maximum Circuit
Size: Simplified, Truly Uniform](https://arxiv.org/abs/2310.17762)
- [Symmetric exponential time requires near-maximum circuit size](https://eccc.weizmann.ac.il/report/2023/144/)

### Hardness Magnification

Hardness magnification is a striking phenomenon which shows that weak fixed-polynomial lower bounds (say, $n^{1+\varepsilon}$) for certain problems can be magnified to strong super-polynomial lower bounds, and therefore suggests a way to solving some long-standing open problems in complexity theory.

- [Hardness Magnification for Natural Problems](https://eccc.weizmann.ac.il/report/2018/139/)
- [Hardness magnification near state-of-the-art lower bounds](https://eccc.weizmann.ac.il/report/2018/158/)
- [Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems](https://eccc.weizmann.ac.il/report/2019/075/)
- [Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes](http://people.csail.mit.edu/rrw/MCSP-MKTP-stoc19.pdf)
- [Hardness Magnification for all Sparse NP Languages](https://eccc.weizmann.ac.il/report/2019/118/)

This paper proves some results related to hardness magnification, quantified derandomization, and explicit obstructions:

- [Sharp Threshold Results for Computational Complexity](https://eccc.weizmann.ac.il/report/2020/065/)

### Non-rigidity of Matrices
Constructing rigid matrices is a well-known but notoriously difficult problem in complexity theory. There are some surprising recent works showed that several candidate matrices are not as rigid as we thought.

See this paper and the references therein:

- [Fourier and Circulant Matrices are Not Rigid](https://arxiv.org/abs/1902.07334)

### Karp-Lipton Theorems
See this paper and the references therein:

- [Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems](https://eccc.weizmann.ac.il/report/2019/075/)

## Arithmetic Circuits / Algebraic Complexity

### Hardness vs Randomness for Arithmetic Circuits
See this paper and the references therein:

- [Derandomization from Algebraic Hardness: Treading the Borders](https://eccc.weizmann.ac.il/report/2019/065/)

## Quantum Complexity Theory

### Quantum Advantage for Shallow Circuits
See this paper and the references therein:

- [Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits](http://eccc.weizmann.ac.il/report/2019/089/)

### Oracle Separation for BQP from PH
See the following two papers:

- [Oracle Separation of BQP and PH](http://eccc.weizmann.ac.il/report/2018/107/)
- [Pseudorandom Generators from Polarizing Random Walks](https://eccc.weizmann.ac.il/report/2018/015/)

### Polynomial Methods in Quantum Complexity
A few recent papers in this area:

- [Quantum Lower Bounds for Approximate Counting via Laurent Polynomials](https://arxiv.org/abs/1904.08914)
- [The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials](https://arxiv.org/abs/1710.09079)

Some older papers in this area:

- [Quantum Lower Bound for the Collision Problem](https://www.scottaaronson.com/papers/collision.pdf)
- [Quantum lower bounds for the collision and the element distinctness problems](https://dl.acm.org/citation.cfm?id=1008735)

### Lower Bounds for Quantum Merlin-Author Protocols

See the following papers and the references therein:

- [Polynomial degree vs. quantum query complexity](https://core.ac.uk/download/pdf/82107059.pdf)
- [Vanishing-Error Approximate Degree and QMA Complexity](https://eccc.weizmann.ac.il/report/2019/121/)
- [Impossibility of Succinct Quantum Proofs for Collision-Freeness](https://www.scottaaronson.com/papers/szkqma.pdf)

### Quantum Advantage

See the following papers and the references therein:

- [Complexity-Theoretic Foundations of Quantum Supremacy Experiments](https://eccc.weizmann.ac.il//report/2016/200/)
- [Quantum Computational Supremacy](https://arxiv.org/pdf/1809.07442)
- [Quantum Supremacy and the Complexity of Random Circuit Sampling](https://arxiv.org/abs/1803.04402)

## Derandomization

### Derandomization of Stronger Complexity Classes

Stronger circuit lower bounds imply $( \textsf{AM} = \textsf{NP} )$. See the following paper and its references:

- [Pseudorandomness for Approximate Counting and Sampling](https://eccc.weizmann.ac.il//eccc-reports/2004/TR04-086/index.html)

### Derandomization under uniform assumptions

The influential paradigm of hardness vs randomness shows that under certain non-uniform assumptions $( \textsf{E}$ is not in $\text{i.o.SIZE}[2^{o(n)}] , \textsf{P} = \textsf{BPP} )$. There is also a line of work studying what type of derandomization we can get from uniform assumptions (such as $\textsf{E} \neq \textsf{BPP}$ ). See the following papers and the references therein:

- [Randomness vs. Time: De-randomization under a uniform assumption](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW98/proc.pdf)
- [Uniform Hardness Versus Randomness Tradeoffs For Arthur–Merlin Games](http://www.cs.tau.ac.il/~amnon/Papers/GST.cc.pdf)
- [Pseudorandomness and Average-Case Complexity via Uniform Reductions](https://people.seas.harvard.edu/~salil/research/uniform-cc.pdf)
- [Low-end uniform hardness vs. randomness tradeoffs for AM](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.154.5218&rep=rep1&type=pdf)

### Quantified Derandomization

See these papers and the references therein:

- [Quantified derandomization of linear threshold circuits](https://eccc.weizmann.ac.il/report/2017/145/)
- [Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials](https://eccc.weizmann.ac.il//report/2016/191/)

### Nearly-Optimal Derandomization

- [Nearly Optimal Pseudorandomness From Hardness](https://eccc.weizmann.ac.il/report/2019/099)
- [Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost](https://eccc.weizmann.ac.il/report/2020/148/)

### Derandomization of low space algorithms

#### Connectivity in LOGSPACE

The following paper proved the breakthrough result that connectivity is in LOGSPACE:

- [Undirected Connectivity in Log-Space](https://omereingold.files.wordpress.com/2014/10/sl.pdf)

It builds on the paper:

- [Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders](https://omereingold.files.wordpress.com/2014/10/zigzag-annals.pdf)

The following paper shows if it can be extended a bit, then we can derandomize all of randomized log space:

- [Pseudorandom Walks on Regular Digraphs and the RL vs. L Problem](https://omereingold.files.wordpress.com/2017/06/regular.pdf)

#### PRG for Branching Programs

There are some recent exciting developments on PRG (or HSG) for branching programs:

- [Pseudorandom Generators for Width-3 Branching Programs](https://eccc.weizmann.ac.il/report/2018/112/)
- [Pseudorandom Generators for Read-Once Branching Programs, in any Order](https://eccc.weizmann.ac.il/report/2018/147/)
- [Simple Optimal Hitting Sets for Small-Success RL](https://eccc.weizmann.ac.il/report/2018/063/)
- [Pseudorandom Pseudo-Distributions with Near-Optimal Error for Read-Once Branching Programs](https://eccc.weizmann.ac.il/report/2017/161/)
- [Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace](https://arxiv.org/abs/1610.01199)

There are also some more classic papers on this topic:

- [Pseudorandom Generators For Space-Bounded Computation](https://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Nisan_PRG.pdf)
- [Pseudorandomness for Network Algorithms](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/INW94/proc.pdf)
- [BP_HSPACE(S) ⊆ DSPACE(S^(3/2))](https://render.githubusercontent.com/render/math?math=%5Ctext%7BBP%7D_%7B%5Ctext%7BH%7D%7D%5Ctext%7BSPACE%7D%28S%29%20%5Csubseteq%20%5Ctext%7BDSPACE%7D%28S%5E%7B3%2F2%7D%29)

### Unconditional construction of PRGs

There are some recent works on PRG for a variety of computational models:

- [Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas](https://eccc.weizmann.ac.il/report/2018/183/)
- [Pseudorandom Generators from Polarizing Random Walks](https://eccc.weizmann.ac.il/report/2018/015/)
- [Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates](https://eccc.weizmann.ac.il/report/2018/155/)

Some earlier works:

- [Pseudorandomness from Shrinkage](https://eccc.weizmann.ac.il/report/2012/057/)
- [Pseudorandom Generators for Polynomial Threshold Functions](https://arxiv.org/abs/0910.4122)
- [Pseudorandom Generators for Combinatorial Shapes](https://eccc.weizmann.ac.il/report/2010/176/)

### Typical-Correct Derandomization

See the following papers:

- [Derandomization that is rarely wrong from short advice that is typically good](https://eccc.weizmann.ac.il//eccc-reports/2002/TR02-039/index.html)
- [Pseudorandom Generators, Typically-Correct](http://pages.cs.wisc.edu/~dieter/Papers/r-typical-full.pdf)

Derandomization, and Circuit Lower Bounds
Typically-Correct Derandomization for Small Time and Space

## Explicit Constructions
The following recent paper proves some interesting complexity characterizations of what it would mean to “derandomize the probabilistic method” for certain problems. The arguments are fairly accessibe and the results have many interesting imlications:

[The Hardest Explicit Construction](https://arxiv.org/abs/2106.00875)

## Query Complexity and Communication Complexity
### Lifting Theorems
Recently, there is a line of beautiful works focusing on the so-called *lifting theorems*, which shows query complexity lower bounds (which is usually easier to prove) can be *lifted* to a communication complexity lower bound (which is usually harder to prove).

See this paper and the references therein

[Query-to-Communication Lifting Using Low-Discrepancy Gadgets](https://eccc.weizmann.ac.il/report/2019/103)

### Number-on-Forhead (NOF) Complexity

Another well-studied model for communication complexity is the Number-on-Forhead model. In this model, three players Alice, Bob and Charlie each have their own inputs $x,y,z$ written on their foreheads and they want to compute some function $f(x,y,z)$. As suggested by the name of the model, the players do not have access to their own input, but have access to the other two inputs. Recently there has been substantial progress made towards the separation between randomized and deterministic communication complexity in this model.

See this paper and the references therein

[Explicit separations between randomized and deterministic
Number-on-Forehead communication](https://arxiv.org/abs/2308.12451)

## Fine-Grained Complexity
### Hardness of Approximation in Fine-Grained Complexity
The past few years have seen conjectures from fine-grained complexity being used to prove interesting hardness results for various approximation problems, using interesting reduction frameworks. A good starting paper in this area is the following:

[Distributed PCP Theorems for Hardness of Approximation in *P*](https://arxiv.org/abs/1706.06407)

#### Algebraic Methods in Fine-Grained Complexity
The program of fine-grained complexity is very successful at exact problems (problems in which an exact solution is sought). But we know less about the exact running time of approximation problems in *P*. To resolve these questions there are recent works apply algebraic methods to fine-grained complexity.

This paper and the references therein offer some applications of this type:

[On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic](https://arxiv.org/abs/1812.00901)

The following paper is a sort of “sequel” to the one above, and provides hardness of approximation for some more general problems using some similar, but more sophisticated, arguments:

[Applications of Random Algebraic Constructions to Hardness of Approximation](https://arxiv.org/abs/2111.05518)

## Proof Systems
### Linear Size LTCs (Locally Testable Codes)
[Locally Testable Codes with constant rate, distance, and locality](https://arxiv.org/abs/2111.04808)

### Near Linear Size PCPs
See the following papers

- [On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs](https://eccc.weizmann.ac.il/report/2012/045/)
- [The PCP Theorem by Gap Amplification](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf)
- [Short PCPs with polylog query complexity](http://madhu.seas.harvard.edu/papers/2005/rspcpp-full.pdf)
- [Short PCPs Verifiable in Polylogarithmic Time](http://madhu.seas.harvard.edu/papers/2005/bghsv2-full.pdf)
- [Robust PCPs of Proximity, Shorter PCPs and Applications to Coding](http://madhu.seas.harvard.edu/papers/2004/bghsv-full.pdf)

### Doubly-efficient proof systems
See the following papers

- [Efficient Batch Verification for UP](https://eccc.weizmann.ac.il/report/2018/022/)
- [Simple doubly-efficient interactive proof systems for locally-characterizable sets](https://eccc.weizmann.ac.il/report/2017/018/)
- [Constant-Round Interactive Proofs for Delegating Computation](https://eccc.weizmann.ac.il/report/2016/061/)

### PCP-like proof systems

See the following papers

- [Interactive Oracle Proofs with Constant Rate and Query Complexity](https://eprint.iacr.org/2016/324)
- [Interactive Oracle Proofs](https://eprint.iacr.org/2016/116)

## Geometric Complexity Theory
### Recent Developments

- [No occurrence obstructions in geometric complexity theory](https://arxiv.org/abs/1604.06431)
- [On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions](https://arxiv.org/abs/1901.04576)

## Other Topics
### NP-hardness of the 2-to-2 Game
Unique Game Conjecture, which states 1-to-1 games are NP-hard, is one of the most important conjectures in complexity theory. Several recent works have shown 2-to-2 games, a close variant of 1-to-1 games, are NP-hard.

See this paper and the references therein

[Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion](https://eccc.weizmann.ac.il/report/2018/006)

### Time-Space Lower Bounds for Learning
See this paper and the references therein:

[Time-Space Lower Bounds for Two-Pass Learning](https://eccc.weizmann.ac.il/report/2019/071)

### Instantiations of the Relativization Barrier

See the following papers and the references therein:

[Oracles Are Subtle But Not Malicious](https://arxiv.org/pdf/cs/0504048.pdf)

### Algebrization Barrier to Circuit Lower Bounds

See the following papers:

- [Algebrization: A New Barrier in Complexity Theory](http://www.scottaaronson.com/papers/alg.pdf)
- [Affine Relativization: Unifying the Algebrization and Relativization Barriers](https://eccc.weizmann.ac.il//report/2016/040/)

### Natural Proofs and Natural Properties

See these papers and the references therein:

- [The Power of Natural Properties as Oracles](https://eccc.weizmann.ac.il/report/2017/023)
- [Algorithms from Natural Lower Bounds](https://eccc.weizmann.ac.il/report/2016/008)

### Necessary Conditions for Lower Bounds

Relativization, natural proofs, and algebrization present some barriers to proving certain lower bounds. The following recent paper takes a complementary view and, among other results, demonstrates some **necessary** conditions and implications of proving certain lower bounds:

- [Constructive Separations and Their Consequences](https://eccc.weizmann.ac.il/report/2021/159/)

### Near-Optimal Construction of Extractor

See the following papers:

- [Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers](https://arxiv.org/pdf/0901.2529.pdf)
- [Unbalanced Expanders and Randomness Extractors from Parvaresh–Vardy Codes](https://www.cs.cmu.edu/~venkatg/pubs/papers/PV-condenser.pdf)
- [Kakeya sets, new mergers and old extractors](https://www.cs.princeton.edu/~zdvir/papers/DvirWigderson08.pdf)

### Recent Developments on Sign-rank / threshold of AC^0 Circuits

See this paper and the references therein:

- [Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0](https://arxiv.org/abs/1901.00988)

### Limits on Instance Compression

See the following papers:

- [On the Compressibility of NP Instances and Cryptographic Applications](http://www.wisdom.weizmann.ac.il/~naor/PAPERS/compressibility.pdf)
- [Infeasibility of Instance Compression and Succinct PCPs for NP](https://people.csail.mit.edu/rrw/presentations/fortnow-santhanam.pdf)
- [New Limits to Classical and Quantum Instance Compression](http://people.cs.uchicago.edu/~adrucker1/newlimits.pdf)

### Tree Evaluation

- [Pebbles and Branching Programs for Tree Evaluation](https://arxiv.org/abs/1005.2642)
- [Tree Evaluation is in Space $O(\log n · \log \log n)$](https://www.cs.toronto.edu/~mertz/papers/cm23.tree_evaluation_is_in_space_lognloglogn.pdf)

## Minimum Circuit Size Problem

### Recent Concrete Lower Bounds for MCSP

This line of work proves several concrete lower bounds for the MCSP problem. They show that most state-of-the-art circuit lower bounds can be proved for the MCSP problems as well.

- [Circuit Lower Bounds for MCSP from Local Pseudorandom Generators](https://eccc.weizmann.ac.il/report/2019/022)
- [AC^0[p] Lower Bounds and NP-Hardness for Variants of MCSP](https://eccc.weizmann.ac.il/report/2019/021)
- [AC^0[p] Lower Bounds against MCSP via the Coin Problem](https://eccc.weizmann.ac.il/report/2019/018)

For even more recent results, see the following papers and their references:

- [NP-Hardness of Circuit Minimization for Multi-Output Functions](https://eccc.weizmann.ac.il/report/2020/021/download)
- [Constant Depth Formula and Partial Function Versions of MCSP are Hard](https://www.rahulilango.com/papers/FOCS2020.pdf)
- [The Minimum Formula Size Problem is (ETH) Hard](https://www.rahulilango.com/papers/MFSP-hard.pdf)

### Average-Case to Worst-Case Reduction for MCSP
A fundamental problem in complexity is whether there is a worst-case to average-case reduction for NP-complete problems. It has been shown that black-box reductions (which captures most of the previous reductions in complexity theory) cannot establish worst-case to average-case reductions for problems outside of $\textsf{NP}∩ \textsf{coNP}$.

In the following significant work, worst-case to average-case reduction is shown for a certain version of MCSP problem, which is believed to be not in$\textsf{NP}∩ \textsf{coNP}$

[Non-black-box Worst-case to Average-case Reductions within NP](https://eccc.weizmann.ac.il/report/2018/138)

See also the follow-up work below.

[On Nonadaptive Security Reductions of Hitting Set Generators](https://eccc.weizmann.ac.il/report/2019/025)

### NP-Hardness for MCSP Problems
Whether MCSP is NP-complete is an annoyingly open question in complexity theory. While the answer is still not clear, some works are showing certain variants of MCSP is NP-complete, and some other works showing there is circuit lower bounds barrier for proving MCSP is NP-complete.

**1: On NP-hardness for variants of MCSP**

See this paper and the references therein

[NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits](https://eccc.weizmann.ac.il/report/2018/030)

**2: On Barriers for proving MCSP is NP-complete**

See this paper and the references therein

[On the (Non) NP-Hardness of Computing Circuit Complexity](http://theoryofcomputing.org/articles/v013a004/)