# Computational Complexity (16w5044)

Arriving in Banff, Alberta Sunday, September 4 and departing Friday September 9, 2016

## Organizers

Paul Beame (University of Washington)

Russell Impagliazzo (University of California, San Diego)

Avi Wigderson (Institute for Advanced Study)

Valentine Kabanets (Simon Fraser University)

Toniann Pitassi (University of Toronto)

## Objectives

Complexity theory has often been using (and contributing to) a number of different areas of mathematics: logic, combinatorics, information theory, algebra, geometry, and analysis, to name just a few. Below we sample a few exciting recent developments in complexity.

Building on the work by Valiant et al., Agrawal and Vinay observed that even very shallow (depth 4) arithmetic circuits are powerful enough to simulate general arithmetic circuits (with a certain increase in size). Later this result has been improved by Koiran and Tavenas, showing that a lower bound $n^{\omega(\sqrt{n})}$ for a very special kind of arithmetic depth 4 circuits (homogeneous depth 4 circuits).would imply a superpolynomial lower bound for general arithmetic circuits.

These results clarify why it's so difficult to prove lower bounds even for small constant-depth arithmetic circuits. On the other hand, they also provide a potentially successful approach to proving general lower bounds by focusing on shallow arithmetic circuits of certain particular form. There have been a number of recent exciting results in that direction, culminating with the work of Kayal et al., and Kumar and Saraf, that gives a lower bound $n^{\Omega(\sqrt{n})}$ for depth 4 homogeneous arithmetic circuits, bringing us tanatalizingly close to the holy grail of arithmetic circuit complexity --- proving that Permanent requires superpolynomial arithmetic circuit complexity.

Determining if a given arithmetic circuit computes an identically zero polynomial (Polynomial Identity Testing problem) is a central problem in derandomization and in (arithmetic) circuit complexity. While devising an efficient deterministic algorithm for PIT remains a major open question in complexity theory, there has been some for restricted classes of arithmetic circuits, often with the help of geometric ideas (e.g., Sylvester-Gallai analogs).

Very recently, Kopparty et al. proved that PIT is polynomial-time equivalent to the problem of deterministic multivariate polynomial factorization, another outstanding open problem in derandomization.

A breakthrough lower bound was proved by Williams, showing that nondeterministic exponential-time computable problems require superpolynomial constant-depth circuits with arbitrary counting (mod m) gates; previously, only the case of prime moduli m was known. Recently, this bound was strengthened by Williams to a more powerful class of circuits.

These and related lower bound results exploit a deep connection between circuit lower bounds and SAT algorithms (or pseudorandom generators) for the same class of circuits. In particular, the classical lower bounds for constant-depth circuits ($AC^0$) and $n^3$-size de Morgan formulas have been recently shown to yield improved (better than naive brute force) SAT algorithms for the same class of circuits [Impagliazzo et al., Santhanam, and Komargodski et al.] as well as new pseudorandom generators [Impagliazzo et al.].

There has also been more progress on strengthening classical lower bounds for formulas. For example, Komargodski et al. get a polynomial-time computable function that can't be computed well on average by any de Morgan formula of size below $n^3$.

Very recently, Gavinsky et al. made a step towards resolving the KRW Composition Conjecture (about the depth complexity of the composition of two boolean functions), which would imply a new circuit lower bound (against the class $NC^1$ of $O(\log n)$-depth boolean circuits). They proved a special case of the KRW conjecture for the composition of a boolean function and a universal relation. The proof relies on the information-theoretic techniques that have been very useful in a number of recent results in communication complexity.

Recently, Grochow and Pitassi introduced a new proof system, the Ideal Proof System (IPS), that has tight connections to (algebraic) circuit complexity. Namely, super-polynomial lower bounds on any Boolean tautology in IPS implies that the permanent does not have polynomial-size algebraic circuits (VNP is not equal to VP). As a corollary to the proof, super-polynomial lower bounds on the number of lines in Polynomial Calculus proofs (a previously studied proof system) implies the Permanent versus Determinant Conjecture. Prior to this work, there was no proof system for which lower bounds on an arbitrary tautology implied any computational lower bound. This work begins to shed light on why proof complexity lower bounds have been so difficult to obtain, and highlights the polynomial identity testing (PIT) problem as central to this issue. More specifically, IPS is polynomially equivalent to standard Frege systems if a natural set of propositional axioms, satisfied by any Boolean circuit computing PIT, has subexponential-size Frege proofs. This work raises many exciting questions about connections between PIT, algebraic circuit complexity and proof complexity, and the BIRS workshop will bring experts in all of these areas together.

While the diversity of new tools and ideas used in modern complexity theory is very welcome, it also brings new challenges. The main challenge is to ensure that the field stays united, and that different sub-areas of computational complexity interact with each other. Such exchange of ideas is of utmost importance for the continued progress in complexity theory. Another challenge is to ensure that the complexity community remains focused on the fundamental problems in the field, such as the "P vs NP" and related big open questions.

The proposed workshop aims at addressing both of these challenges. We plan to bring together some of the most active researchers in various sub-areas of computational complexity to review the state of the art, examine the power and limitations of new techniques, and suggest new directions for research, with the emphasis on the fundamental open questions in complexity theory. We also plan to invite a number of senior grad students and postdocs to ensure that the young researchers are aware of the ideas and tools from different sub-areas of complexity theory, and to encourage their interest and willingness to work on hard open problems. We believe that such a workshop will help keep the complexity theory a vibrant field of research, with fruitful interactions among different branches of complexity and mathematics, and the sharp focus on the foundational questions.

#### Arithmetic circuit complexity

Building on the work by Valiant et al., Agrawal and Vinay observed that even very shallow (depth 4) arithmetic circuits are powerful enough to simulate general arithmetic circuits (with a certain increase in size). Later this result has been improved by Koiran and Tavenas, showing that a lower bound $n^{\omega(\sqrt{n})}$ for a very special kind of arithmetic depth 4 circuits (homogeneous depth 4 circuits).would imply a superpolynomial lower bound for general arithmetic circuits.

These results clarify why it's so difficult to prove lower bounds even for small constant-depth arithmetic circuits. On the other hand, they also provide a potentially successful approach to proving general lower bounds by focusing on shallow arithmetic circuits of certain particular form. There have been a number of recent exciting results in that direction, culminating with the work of Kayal et al., and Kumar and Saraf, that gives a lower bound $n^{\Omega(\sqrt{n})}$ for depth 4 homogeneous arithmetic circuits, bringing us tanatalizingly close to the holy grail of arithmetic circuit complexity --- proving that Permanent requires superpolynomial arithmetic circuit complexity.

#### Polynomial Identity Testing (PIT)

Determining if a given arithmetic circuit computes an identically zero polynomial (Polynomial Identity Testing problem) is a central problem in derandomization and in (arithmetic) circuit complexity. While devising an efficient deterministic algorithm for PIT remains a major open question in complexity theory, there has been some for restricted classes of arithmetic circuits, often with the help of geometric ideas (e.g., Sylvester-Gallai analogs).

Very recently, Kopparty et al. proved that PIT is polynomial-time equivalent to the problem of deterministic multivariate polynomial factorization, another outstanding open problem in derandomization.

#### Boolean circuit complexity and SAT algorithms

A breakthrough lower bound was proved by Williams, showing that nondeterministic exponential-time computable problems require superpolynomial constant-depth circuits with arbitrary counting (mod m) gates; previously, only the case of prime moduli m was known. Recently, this bound was strengthened by Williams to a more powerful class of circuits.

These and related lower bound results exploit a deep connection between circuit lower bounds and SAT algorithms (or pseudorandom generators) for the same class of circuits. In particular, the classical lower bounds for constant-depth circuits ($AC^0$) and $n^3$-size de Morgan formulas have been recently shown to yield improved (better than naive brute force) SAT algorithms for the same class of circuits [Impagliazzo et al., Santhanam, and Komargodski et al.] as well as new pseudorandom generators [Impagliazzo et al.].

There has also been more progress on strengthening classical lower bounds for formulas. For example, Komargodski et al. get a polynomial-time computable function that can't be computed well on average by any de Morgan formula of size below $n^3$.

Very recently, Gavinsky et al. made a step towards resolving the KRW Composition Conjecture (about the depth complexity of the composition of two boolean functions), which would imply a new circuit lower bound (against the class $NC^1$ of $O(\log n)$-depth boolean circuits). They proved a special case of the KRW conjecture for the composition of a boolean function and a universal relation. The proof relies on the information-theoretic techniques that have been very useful in a number of recent results in communication complexity.

#### Proof complexity, circuit complexity, and PIT

Recently, Grochow and Pitassi introduced a new proof system, the Ideal Proof System (IPS), that has tight connections to (algebraic) circuit complexity. Namely, super-polynomial lower bounds on any Boolean tautology in IPS implies that the permanent does not have polynomial-size algebraic circuits (VNP is not equal to VP). As a corollary to the proof, super-polynomial lower bounds on the number of lines in Polynomial Calculus proofs (a previously studied proof system) implies the Permanent versus Determinant Conjecture. Prior to this work, there was no proof system for which lower bounds on an arbitrary tautology implied any computational lower bound. This work begins to shed light on why proof complexity lower bounds have been so difficult to obtain, and highlights the polynomial identity testing (PIT) problem as central to this issue. More specifically, IPS is polynomially equivalent to standard Frege systems if a natural set of propositional axioms, satisfied by any Boolean circuit computing PIT, has subexponential-size Frege proofs. This work raises many exciting questions about connections between PIT, algebraic circuit complexity and proof complexity, and the BIRS workshop will bring experts in all of these areas together.

While the diversity of new tools and ideas used in modern complexity theory is very welcome, it also brings new challenges. The main challenge is to ensure that the field stays united, and that different sub-areas of computational complexity interact with each other. Such exchange of ideas is of utmost importance for the continued progress in complexity theory. Another challenge is to ensure that the complexity community remains focused on the fundamental problems in the field, such as the "P vs NP" and related big open questions.

The proposed workshop aims at addressing both of these challenges. We plan to bring together some of the most active researchers in various sub-areas of computational complexity to review the state of the art, examine the power and limitations of new techniques, and suggest new directions for research, with the emphasis on the fundamental open questions in complexity theory. We also plan to invite a number of senior grad students and postdocs to ensure that the young researchers are aware of the ideas and tools from different sub-areas of complexity theory, and to encourage their interest and willingness to work on hard open problems. We believe that such a workshop will help keep the complexity theory a vibrant field of research, with fruitful interactions among different branches of complexity and mathematics, and the sharp focus on the foundational questions.