CSCI 5170: Computational Complexity

The Chinese University of Hong Kong, Spring 2016

Final project information

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

Presentation Schedule

Tuesday 19 April
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