##### Dagstuhl Seminar 16411

### Algebraic Methods in Computational Complexity

##### ( Oct 09 – Oct 14, 2016 )

##### Permalink

##### Organizers

- Valentine Kabanets (Simon Fraser University - Burnaby, CA)
- Thomas Thierauf (Hochschule Aalen, DE)
- Jacobo Torán (Universität Ulm, DE)
- Christopher Umans (CalTech - Pasadena, US)

##### Contact

- Andreas Dolzmann (for scientific matters)
- Simone Schilke (for administrative matters)

##### Impacts

- A Deterministic Algorithm for Testing the Equivalence of Read-Once Branching Programs with Small Discrepancy : article in LNCS 10307 : CiE 2017 - Arnold, Stefan; Toran, Jacobo - Berlin : Springer, 2017. - pp. 119-128 - (Lecture notes in computer science ; 10307 : article).
- Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable - Arvind, Vikraman; Köbler, Johannes; Kuhnert, Sebastian; Toran, Jacobo - Cornell University : arXiv.org, 2017.
- The border support rank of two-by-two matrix multiplication is seven - Bläser, Markus; Christandl, Matthias; Zuiddam, Jeroen - Cornell University : arXiv.org, 2017.

Computational Complexity is concerned with the resources that are required for algorithms to detect properties of combinatorial objects and structures.

It has often proven true that the best way to argue about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques. The Razborov-Smolensky polynomial-approximation method for proving constant-depth circuit lower bounds, the PCP characterization of NP, and the Agrawal-Kayal-Saxena polynomial-time primality test are some of the most prominent examples.

The algebraic theme continues in some of the most exciting recent progress in computational complexity. There have been significant recent advances in algebraic circuit lower bounds, and the so-called chasm at depth 4 suggests that the restricted models now being considered are not so far from ones that would lead to a general result. There have been similar successes concerning the related problems of polynomial identity testing and circuit reconstruction in the algebraic model (and these are tied to central questions regarding the power of randomness in computation).

Another surprising connection is that the algebraic techniques invented to show lower bounds now prove useful to develop efficient algorithms.

For example, Williams showed how to use the polynomial method to obtain faster all-pair-shortest-path algorithms. This emphases once again the central role of algebra in computer science.

This Dagstuhl Seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic methods in a variety of settings. Researchers in these areas are relying on ever more sophisticated and specialized mathematics and this seminar can play an important role in educating a diverse community about the latest new techniques, spurring further progress.

The seminar brought together more than 40 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed the great importance of such techniques for theoretical computer science. We had 25 talks, most of them lasting about 40 minutes, leaving ample room for discussions. In the following we describe the major topics of discussion in more detail.

#### Circuit Complexity

This is an area of fundamental importance to Complexity. Circuit Complexity was one of the main topics in the seminar. Still it remains a big challenge to prove strong upper and lower bounds. Also Polynomial Identity Testing (PIT) plays a central role.

The seminar started with a talk by *Steve Fenner*. In a breakthrough result, he showed how to solve the perfect matching problem in bipartite graphs (almost) efficiently in parallel, by circuits of quasi-polynomial size and O(log^2 n) depth (in quasi-NC). This solves a problem open since more than 30 years. *Rohit Gurjar*} showed how to extend the result even further to *linear matroid intersection*, where bipartite perfect matching is a special case of.

Both of the above results can be read as a singularity test of certain symbolic matrices. We had several talks dealing with determining singularity or computing the rank of a symbolic matrix. *Rafael Oliveira* presented an efficient algorithm for the symbolic singularity problem in the *non-commutative* setting. In the *commutative* setting, the complexity is a major open problem. Many other important problems reduce to it.
*Markus Bläser* presented an *approximation algorithm* (PTAS) for the rank of a symbolic matrix. Surprisingly, this is achieved with a greedy-algorithm. *Kristoffer Hansen* showed a different kind of approximation for low rank binary matrices.

We have seen some great work on *Polynomial Identity Testing* (PIT)
and circuit lower bounds recently, in particular on depth-3 and depth 4 circuits, and on arithmetic branching programs, which has brought us very
close to statements that are known to imply VP not= VNP, the analogue of the P vs. NP question in the arithmetic world. With respect to PIT, an ambitious goal is to come up with a hitting set construction for a specific model. A hitting set is a set of instances such that every non-zero polynomial in the model has a non-root in the set. This would solve the PIT problem in the *black box* model.

PIT is known to be efficiently solvable by *randomized* algorithms,
for example when we consider arithmetic circuits. Things get a bit different when we consider *noncummutative* circuits. Now the standard test cannot be directly applied because the polynomials can have exponential degree, and hence doubly exponentially many monomials. *V. Arvind* presented
a randomized polynomial identity test for noncommutative arithmetic circuits
for the case when the polynomial has only exponentially many monomials.

One of the most successful methods for proving lower bounds for arithmetic circuits is to consider the dimension of the span of the *partial derivatives* of a polynomial. *Pascal Koiran* considered the complexity of the problem to compute this dimension. He showed that it is #P-hard. It remained open whether the problem is #P-complete.

Another important notion when proving lower bounds is the *algebraic independence* of arithmetic circuits. In 2015, Kumar and Saraf presented lower bounds and hitting sets for a class of depth-4 circuits that have low algebraic rank. Unfortunately, their technique requires base fields of characteristic zero, or at least exponentially large characteristic.
*Nitin Saxena* closed this gap and showed how to make the approach work over *every* field.

*Michael Forbes* showed that lower bounds for certain algebraic circuits imply lower bounds in proof complexity.

*Or Meir* talked on one of the major open problems in complexity theory: proving super-polynomial lower bounds on the size of formulas.
Karchmer, Raz, and Wigderson suggested an approach to this problem. The *KRW-conjecture* states that the formula complexity of two functions f and g roughly adds up when we consider the composed function gcirc f.
They showed that the conjecture implies super-polynomial formula lower bounds
In his talk, Or Meir did a step to prove the conjecture: he proved a special case, namely when f is the parity-function. His proof uses techniques from communication complexity.

Valiant introduced the arithmetic analogue of classes P and NP.
Very roughly, the class VP contains all multivariate polynomials that can be computed (non-uniformly) by polynomial-size arithmetic circuits,
and the class VNP contains all multivariate polynomials that have coefficients
computable by VP-circuits. The question whether VP is different from VNP
plays the role of the P-NP question in algebraic complexity theory.
Valiant showed that the permanent is complete for VNP. But for VP, only artificially constructed functions were known to be complete. In her talk, *Meena Mahajan* described several polynomial families complete for VP and for VNP, based on the notion of graph homomorphism polynomials.

#### Complexity

Since the famous AKS-primality test, prime numbers can be recognized efficiently. The *construction* of prime numbers is still a challenging task. The best known deterministic algorithm have only exponential running time. *Rahul Santhanam* presented a randomized subexponential time algorithm that outputs primes, and only primes, with high probability,
and moreover, the output is mostly the same prime. This is called a *zero-error pseudo-deterministic* algorithm.

Since the famous Isolation Lemma of Mulmuley, Vazirani, Vazirani, researchers recognized the power of isolation. For example, the bipartite perfect matching and the matroid intersection algorithms mentioned above, both rely on isolating a minimum weight solution, *Nutan Limaye* studied the problem of isolating an s-t-path in a directed graph. She proved that a randomized logspace algorithm that isolates such a path can be used to show NL subseteq L/poly.

Derandomization is an area where there are tight connections between lower bounds and algorithms. Strong enough circuit lower bounds can be used to construct pseudo-random generators that can then be used to simulate randomized algorithms with only polynomial overhead. The polynomial overhead is fine for algorithms running in polynomial time. However, in case of subexponential randomized algorithms, this overhead makes the resulting deterministic algorithm more or less useless. *Ronen Shaltiel* showed how to overcome this problem by achieving a more modest overhead. He needs, however, stronger lower bounds to begin with. Further talks on pseudo-random generators and randomness extractors were given by *Amnon Ta-Shma* and *William Hoza*.

*Chris Umans* gave an evening talk presenting a recent breakthrough in additive combinatorics, the resolution of the so-called *cap-set conjecture* by Ellenberg and Gijswijt. This result has implications for the Cohn-Umans group-theoretic approach for matrix multiplication, and elsewhere in Complexity.

#### Coding Theory

Error-correcting codes, particularly those constructed from polynomials, i.e. Reed-Solomon codes or Reed-Muller codes, lie at the heart of many
significant results in Computational Complexity. *Shubhangi Saraf* gave a talk on locally-correctable and locally-testable codes. *Swastik Kopparty* generalized the well known decoding algorithm for Reed-Solomon codes to higher dimensions. He presented an efficient algorithm to decode Reed-Muller codes when the evaluation points are an arbitrary product set S^m,
for some m, when S is larger than the degree of the polynomials.

#### Conclusion

As is evident from the list above, the talks ranged over a broad assortment of subjects with the underlying theme of using algebraic and combinatorial techniques. It was a very fruitful meeting and has hopefully initiated new directions in research. Several participants specifically mentioned that they appreciated the particular focus on a common class of *techniques* (rather than end results) as a unifying theme of the workshop. We look forward
to our next meeting!

- Farid Ablayev (Kazan State University, RU) [dblp]
- Vikraman Arvind (The Institute of Mathematical Sciences, India, IN) [dblp]
- Markus Bläser (Universität des Saarlandes, DE) [dblp]
- Andrej Bogdanov (The Chinese University of Hong Kong, HK) [dblp]
- Arkadev Chattopadhyay (TIFR - Mumbai, IN) [dblp]
- Samir Datta (Chennai Mathematical Institute, IN) [dblp]
- Stephen A. Fenner (University of South Carolina - Columbia, US) [dblp]
- Michael A. Forbes (Stanford University, US) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Frederic Green (Clark University - Worcester, US) [dblp]
- Rohit Gurjar (FH Aalen, DE) [dblp]
- Kristoffer Arnsfelt Hansen (Aarhus University, DK) [dblp]
- William Hoza (University of Texas - Austin, US) [dblp]
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Marek Karpinski (Universität Bonn, DE) [dblp]
- Neeraj Kayal (Microsoft Research India - Bangalore, IN) [dblp]
- Pascal Koiran (ENS - Lyon, FR) [dblp]
- Swastik Kopparty (Rutgers University - Piscataway, US) [dblp]
- Arpita Korwar (University Paris-Diderot, FR) [dblp]
- Michal Koucký (Charles University - Prague, CZ) [dblp]
- Andreas Krebs (Universität Tübingen, DE) [dblp]
- Sophie Laplante (University Paris-Diderot, FR) [dblp]
- Nutan Limaye (Indian Institute of Technology - Mumbai, IN) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences, India, IN) [dblp]
- Pierre McKenzie (University of Montréal, CA) [dblp]
- Or Meir (University of Haifa, IL) [dblp]
- Rafael Mendes de Oliveira (Princeton University, US) [dblp]
- David A. Mix Barrington (University of Massachusetts - Amherst, US) [dblp]
- Ryan O'Donnell (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Chandan Saha (Indian Institute of Science - Bangalore, IN) [dblp]
- Rahul Santhanam (University of Oxford, GB) [dblp]
- Shubhangi Saraf (Rutgers University - Piscataway, US) [dblp]
- Nitin Saxena (Indian Institute of Technology - Kanpur, IN) [dblp]
- Uwe Schöning (Universität Ulm, DE) [dblp]
- Ronen Shaltiel (University of Haifa, IL) [dblp]
- Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
- Thomas Thierauf (Hochschule Aalen, DE) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Christopher Umans (CalTech - Pasadena, US) [dblp]
- Nikolay K. Vereshchagin (NRU Higher School of Economics - Moscow, RU) [dblp]
- Amir Yehudayoff (Technion - Haifa, IL) [dblp]
- Jeroen Zuiddam (CWI - Amsterdam, NL) [dblp]

##### Related Seminars

- Dagstuhl Seminar 02421: Algebraic Methods in Quantum and Classical Models of Computation (2002-10-13 - 2002-10-18) (Details)
- Dagstuhl Seminar 04421: Algebraic Methods in Computational Complexity (2004-10-10 - 2004-10-15) (Details)
- Dagstuhl Seminar 07411: Algebraic Methods in Computational Complexity (2007-10-07 - 2007-10-12) (Details)
- Dagstuhl Seminar 09421: Algebraic Methods in Computational Complexity (2009-10-11 - 2009-10-16) (Details)
- Dagstuhl Seminar 12421: Algebraic and Combinatorial Methods in Computational Complexity (2012-10-14 - 2012-10-19) (Details)
- Dagstuhl Seminar 14391: Algebra in Computational Complexity (2014-09-21 - 2014-09-26) (Details)
- Dagstuhl Seminar 18391: Algebraic Methods in Computational Complexity (2018-09-23 - 2018-09-28) (Details)
- Dagstuhl Seminar 22371: Algebraic and Analytic Methods in Computational Complexity (2022-09-11 - 2022-09-16) (Details)

##### Classification

- data structures / algorithms / complexity
- security / cryptology

##### Keywords

- computational complexity
- algebra
- (de-) randomization
- circuits
- coding