Dagstuhl-Seminar 16411
Algebraic Methods in Computational Complexity
( 09. Oct – 14. Oct, 2016 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/16411
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)
Kontakt
- Andreas Dolzmann (für wissenschaftliche Fragen)
- Simone Schilke (für administrative Fragen)
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!
Creative Commons BY 3.0 Unported license
Valentine Kabanets, Thomas Thierauf, Jacobo Torán, and Christopher Umans
- 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]
Verwandte Seminare
- 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)
- Dagstuhl-Seminar 24381: Algebraic and Analytic Methods in Computational Complexity (2024-09-15 - 2024-09-20) (Details)
Klassifikation
- data structures / algorithms / complexity
- security / cryptology
Schlagworte
- computational complexity
- algebra
- (de-) randomization
- circuits
- coding
