Organizer(s):

Swastik Kopparty, Rutgers University

Ran Raz, Princeton University

Description

COVID-19 Notice: This workshop has been cancelled.

Proving lower bounds on the circuit complexity--in both the Boolean and arithmetic settings--is among the most exciting, most challenging, and most important topics in theoretical computer science. The workshop will focus on lower bounds for Boolean and arithmetic circuits and their relations to other computational models, such as communication complexity, as well as relations to other topics in computational complexity, such as pseudorandomness. We will focus on recent breakthrough techniques in the study of topics such as:

• Relations between Boolean circuits, communication complexity, and query complexity;
• Constant-depth arithmetic circuits and their relations to general arithmetic computation;
• Bounded-depth Boolean circuits;
• Monotone circuits and formulas;
• Polynomial identity testing and relations to lower bounds for arithmetic circuits; and
• Lower bounds via algorithms: NEXP vs. ACC etc.

The workshop will bring together researchers working on these topics, with the intent to identify powerful techniques that may play a role in proving future breakthrough lower bounds.

Presented in association with the Special Focus on Lower Bounds in Computational Complexity.