Theory of Computation - Pushing the State-of-Art
PI: Avi Wigderson
co-PI: Ran Raz
The research we propose is on the fundamental problems of computational complexity theory, and
on the cross interactions between them. Some current projects we focus on include:
- Boolean circuit complexity, with a focus on formula lower bounds, and the P \neq NC1 conjecture, especially via an communication complexity and information complexity approach.
- Computational learning theory, with a focus on "non-black-box" modes of learning, including the Restriction Access model and Population Recovery.
- Linear and Semi-definite hierarchies, with a focus of development of lower bound techniques on their power.
- Arithmetic circuit complexity, with a focus on the non-commutative setting.