CSCI 5170: Computational Complexity

Final project information

For your final project, you can do one of the following.

• Do a small research project. You can either choose your own and tell me about it, or pick from the list below.
• Study and reflect upon a work in computational complexity of your choice. To do this kind of project, you will likely need to do some background reading. I expect you to be critical: You will fail if you only reproduce what you read without demonstrating a clear understanding. When presenting your work you are expected to place it in proper context in relation to the material we learned in the course and give your own judgment about the advantages and disadvantages of the work. Two good places to look for possibilities are the ECCC and ArXiv preprints. (A word of warning: The ArXiv papers are not refereed and the ones on ECCC are scrutinized minimally. If you find a serious error bonus points to you!)
• Tell us about computational hardness (and how it is coped with) in your own research area. For this type of project you will need to define your problems and computational models rigorously, justify why your definitions are sensible and explain how they relate to what we learned in class.

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.




Research project possibilities

Here are some possible research projects. I may add more later.

Monotone circuit lower bounds

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?

Average-case complexity of approximate counting and sampling

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.)

Hardness amplification via the hard-core lemma

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.

Presentation Schedule