http://www.dagstuhl.de/16411

09. – 14. Oktober 2016, Dagstuhl Seminar 16411

Algebraic Methods in Computational Complexity

Organisatoren

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

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 6, Issue 10 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente

Summary

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!

License
  Creative Commons BY 3.0 Unported license
  Valentine Kabanets, Thomas Thierauf, Jacobo Torán, and Christopher Umans

Dagstuhl Seminar Series

Classification

  • Data Structures / Algorithms / Complexity
  • Security / Cryptology

Keywords

  • Computational complexity
  • Algebra
  • (de-) randomization
  • Circuits
  • Coding

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.