Computational Complexity Theory

Home             Information             Lectures             Homeworks             References

Suggested Topics for Final Project

Here are some list of topics for the study project for this course. Here are some guidelines for choosing the topic and working on the project. The number within bracket indicates suggested number of people taking it up together. Please select your topic and inform me on or before Jun 3, 2009. Grey color indicates the topic is already taken up !.

• Power of Negations (1) - (Assigned to Kai Jin): We saw Razborov's lower bound for any monotone circuit computing the clique function. This project is to explore extensions of this. The reference is : A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with At Most (1/6)loglog n Negation Gates - K. Amano and A. Maruoka (1998)
• Monotone Circuit Depth Lower Bounds(2) - (Assigned to Hongyu Liang and Jing He)
  By an interesting connection to communication complexity, montone circuit depth lower bounds are obtained for various problems. The idea of this project is to explore some of them.
  • Monotone Circuits for Connectivity Requires Super-logarithmic Depth - Karchmer, Wigderson (SIDM 1990).
  • Monotone Circuits for Matching Require Linear Depth - R. Raz, A. Wigderson (STOC 1990, JACM 1992)
  • Communication Complexity and Monotone Depth - an expository article by Stasys Jukna.

• Structural Properties of PP (1) - (Assigned to Xiaohui Bei)
  This is a classical topic which goes back to the basic randomized algorithms. We skipped over some important structural properties of the class PP in class. This project is to explore the stronger form of these results that uses the power of "polynomials" again. The reference is: PP is closed under intersection by Richard Beigel, Nick Reingold, and Daniel Spielman. (STOC 1991, JCSS 1995)
• Derandomizing Space Bounded Computations(2): We saw Nisan's derandomization of BPL to simulate it using O(log^2 n) space. This result was improved again to O(log^1.5 n) by Saks and Zhou which was further improved by Armoni. This project is to explore some of these papers.
  • BPSPACE(s) subseteq DSPACE(s^1.5) Michael E. Saks, Shiyu Zhou : FOCS 95, JCSS 58(2): 376-403 1999.
  • Time-Space Tradeoff In derandomizing Probablistic Log space classes - Cai, Chakravarthy, Melkebeek (2005)
  • On the Derandomization of Space-Bounded Computations - Roy Armoni (1998)
  • Lecture 20 and Lecture 21 from Jin-Yi Cai's course
  • On recycling the randomness of states in space bounded computation - Ran Raz and Omer Reingold (1999)

• Zero Knowledge Proof Systems(1): We will see interactive proofs briefly in this course. This project explores another related area which is important from the complexity theory and cryptography perspective. This area is vast, but this project could be started on with a specific direction in mind. A good direction is to look at the paper : The Complexity of Zero Knowledge by Salil Vadhan
• Restricted Circuit Lower Bounds(2) - (Assigned to Hao Song and Shiteng Chen)
  In this project we explore the known lower bounds in restricted arithmetic circuits.'
  • Multilinear Formulas for Permanent and Determinant are of Super-Polynomial Size - Ran Raz (STOC 2004)
  • Separation of Multilinear Circuit and Formula Size - Raz Raz (FOCS 2004, ToCS 2006)
  • A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits - Ran Raz, Amir Shpilka, Amir Yahudayoff (FOCS 2007)
  • Lower Bounds and Separations for Constant Depth Multilinear Circuits - Ran Raz, Amir Yahudayoff (CCC 2008)

• General Arithmetic Circuit Lower Bounds(1+1): For the general arithmetic circuit lower bounds we do know some important informations. This project is to explore some of these results.
  • Elusive Functions and Lower Bounds for Arithmetic Circuits - Ran Raz (STOC 2008)
  • Arithmetic Circuits - A Chasm at depth four - Manindra Agarwal, V. Vinay (FOCS 2008)

• More on Derandomization:(1+1): There are plenty of extensions of the Nisan-Wigderson Hardness vs Randomness derandomization paradigm. Each of them is a direction on the frontier on their own.
  • Derandomizing Arthur-Merlin games using hitting sets - Miltersen and Vinodchandran (FOCS 1999, CC 2005)
  • Pseudorandomness for Approximate Counting and Sampling - Shaltiel and Umans (CCC 2005, CC 2006)