For your final project, you have a choice between the following:

- Choose and study a chapter in the Arora-Barak or Goldreich book (or both) that we did not cover in class, or
- Read one or several papers on a complexity theory topic of your choice. There are some topics below, but you can also propose your own.

You will need to write a short survey (due Apr 26) and give a 15 minute presentation on the last week of classes (to be scheduled). The surveys will be submitted and published online on this CSC5170 project wiki. For your presentation you can either use slides or the whiteboard.

You can work individually or in pairs. Please let me know about your
project proposal by email by **Fri Mar 26**. You can write a
paragraph or two about your proposed topic.

4.30-4.45 | Shum Yu Wai, Wu Yi | Average-case complexity |

4.45-5.00 | Steve Chung, Terrence Mak | Statistical zero-knowledge |

5.00-5.15 | Hackson Leung, Leo Cheung | Complexity and cryptography |

5.15-5.30 | Dongfang Cai | Size-depth tradeoffs for threshold circuits |

5.30-6.00 | break | |

6.00-6.15 | Yufei Cai | Kolmogorov complexity |

6.15-6.30 | Zhixin Zhang | Complexity of economic equilibria |

6.30-6.45 | Helic Leung, Tom Chan | Hardness amplification and error-correction |

4.30-4.45 | Yang Li, Ke Liu | Quantum computing |

4.45-5.00 | Chengwei Guo, Fan Li | Complete problems in the poly-time hierarchy |

5.00-5.15 | Yan Kei Mak | Communication complexity |

5.15-5.30 | Andrew Mo | Computational learning theory |

5.30-6.00 | break | |

6.00-6.15 | Chin Ho Lee, Hung Chun Ho | Algebraic complexity |

6.15-6.30 | Jesse Bordoe | Time hierarchy theorems |

6.30-6.45 | Li Ping, Huang Chen | Time hierarchy theorems |

Here are some places where you can look for topics. A good source is the Electronic Colloquium on Computational Complexity where you can find much exciting recent work in the subject. You can also browse recent proceedings of FOCS, STOC, or CCC (the Conference on Computational Complexity). Some of the readings may require too much background reading so feel free to talk to me if you are not sure the project is appropriate. ECCC has several excellent surveys on various topics that you can do (and explore further if you feel motivated).

You are not required to study *all* the papers within a topic. It is
okay to just choose one or two that interest you and report on those. Take a
critical perspective in your reports: Try to identify possible avenues of future
work or limitations of the approaches described in the papers.

In one of the first lectures we saw that P ≠ EXP and NP ≠ NEXP.
These are examples of *time hierarchy theorems*, as they say that given more
time we can do more things. What if we allow the algorithms to use randomness or
non-uniformity?

- Lance Fortnow and Rahul Santhanam: A survey of time hierarchies

- Eric Allender, Michal Koucky: Amplifying Lower Bounds by Means of Self-Reducibility
- Russell Impagliazzo, R Paturi, Michael Saks: Size-depth trade-offs for threshold circuits

- Noam Nisan: Pseudorandom generators for space-bounded computations (see also §8.4 of Goldreich's book)
- Michael Saks and Shiyu Zhou:
RSPACE(
*S*) in DSPACE(*S*^{3/2}) - Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff: Pseudorandom generators for regular branching programs

- Omer Reingold, Luca Trevisan, Salil Vadhan: Pseudorandom walks on regular digraphs and the RL vs. L problem
- Eyal Rozenman and Salil Vadhan: Derandomized squaring of graphs
- Michael Capalbo, Omer Reingold, Salil Vadhan, Avi Wigderson: Randomness conductors and constant-degree lossless expanders

We saw that the existence of certain hard problems for circuits allows us to remove randomness from randomized algorithms. In some settings the opposite is also true: If we can derandomize some class of algorithms, then we have proved a circuit lower bound.

- Valentine Kabanets and Russell Impagliazzo: Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
- Dan Gutfreund and Akinori Kawachi: Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds
- Ryan Williams: Improving exhaustive search implies superpolynomial lower bounds
- Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time

Applications to the Nisan-Wigderson generator extend beyond giving evidence for BPP = P. They can be used to eliminate randomness from interactive proofs, approximate sampling algorithms, and so on. Some of these applications are described in

- Ronen Shaltiel and Chris Umans: Pseudorandomness for Approximate Counting and Sampling
- Ronen Shaltiel and Chris Umans: Simple Extractors for All Min-Entropies and a New Pseudorandom Generator
- Peter Bro Miltersen and N. V. Vinodchandran: Derandomizing Arthur-Merlin games using hitting sets
- Dieter van Melkebeek and Adam Klivans: Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

- Marcus Schaeffer and Chris Umans: Completeness in the polynomial-time hierarchy, parts 一 and 二.
- David Buchfuhrer and Chris Umans: The complexity of Boolean formula minimization
- Chris Umans: The Minimum Equivalant DNF Problem and Shortest Implicants

Average-case complexity studies the hardness of problems on a random input, as opposed to the worst possible input. Is it the case that every problem in NP then becomes easy? The answer is not known. You can start looking at

- Andrej Bogdanov and Luca Trevisan: Average-case complexity