This project focuses on problems in computational complexity theory, with the goal of clarifying the power and limitations of various important classes of algorithms (known as ``complexity classes''). Complexity classes provide the best tools currently available for understanding the computational complexity of real-world computational problems.Recent progress in the field has given rise to (cautious) optimism that routes can be found that avoid some of the known barriers to proving lower bounds on the circuit size required to compute various functions, by capitalizing on the property of ``strong downward self-reducibility''. For problems that possess this property, modest lower bounds can be ``amplified'' to obtain superpolynomial lower bounds. This project aims to investigate the power and applicability of this new approach. In parallel, we will investigate whether certain well-studied proof systems are incapable of proving even the modest lower bounds that would be required in order to bootstrap this ``amplification'' procedure. The project also will investigate other approaches to proving conditional circuit lower bounds.The project will also aim to build on the recent discovery that that the ``counting hierarchy'' (a subclass of PSPACE) is able to perform a large class of numerical computations, and thus contains some complexity classes related to computation over the real field, as well as capturing the complexity of some fundamental problems in numerical analysis. There are several important and seemingly-related problems that are still not known to lie inside the counting hierarchy; this project will investigate whether these problems also are in the counting hierarchy.
|Effective start/end date||8/1/08 → 7/31/12|
- National Science Foundation (National Science Foundation (NSF))