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 NC¹ 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.