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.