For your final project, you have a choice between the following:
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?
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.
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
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