For your final project, you can do one of the following.
You will need to write a report to be turned in on Apr 19 and give a presentation (slides or whiteboard) on the same day. You can work individually or in pairs. The length of the report should be about 3 pages for individual projects and 5 pages for pair projects.
Here are some possible research projects. I may add more later.
In the monotone circuit lower bound for CLIQUE we showed that no small monotone circuit can simultaneously accept all positive instances and reject all negative instances. However there is a simple monotone circuit that accepts all negative instances and rejects all positive ones (what is it?) Can you come up with a possibly different monotone function so that no small monotone circuit can completely distinguish positive or negative in either direction?
Extend the theory of average-case complexity from search and decision to approximate counting and approximate sampling problems. I suggest you start with some examples of such problems that are easy and hard on average, state definitions, and try to relate these two types of problems (they are known to be worst-case equivalent in certain settings, e.g. approximately counting and sampling perfect matchings in graphs.)
Read about Impagliazzo's hard-core lemma and give a alternative proof of Theorem 4 from Lecture 6 (hardness amplification of distributional NP-search problems) using a suitable variant of this lemma.
2.30 | Chengyu Lin | Graph isomorphism in quasi-polynomial time |
2.45 | King On Yung | Quantum lower bounds by polynomials |
3.00 | Xin Huang and Chris Williamson | Hardness amplification via hard-core distributions |
3.15 | Babak Yazdanpanah | Parallel repetition: an information view |
3.30 | break | |
3.30 | Russell Lai and Xinhua Wang | On oblivious RAM lower bounds |
3.45 | Tongxin Li | Bounded distinguishers in differential privacy |
4.00 | Hui Xu | Software obfuscation: theory and practice |
4.15 | break | |
4.30 | Yuxin Su | On the complexity of learning distance metrics |
4.45 | Qiaosheng Zhang | Parallelizing streaming algorithms |
5.00 | Pang Ho Lam | Lower bounds for arithmetic formulas |