https://www.dagstuhl.de/18391
23. – 28. September 2018, Dagstuhl-Seminar 18391
Algebraic Methods in Computational Complexity
Organisatoren
Markus Bläser (Universität des Saarlandes, DE)
Valentine Kabanets (Simon Fraser University – Burnaby, CA)
Jacobo Torán (Universität Ulm, DE)
Christopher Umans (Caltech – Pasadena, US)
Auskunft zu diesem Dagstuhl-Seminar erteilt
Dokumente
Teilnehmerliste
Gemeinsame Dokumente
Motivation
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.
Furthermore, the program of geometric complexity initiated by Mulmuley tries to use methods from algebraic geometry and representation theory to resolve algebraic analogues of the P versus NP question.
These new directions will be in the focus of this Dagstuhl Seminar and reflect the developments in the field since the previous Seminar 14391.
The 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 will play an important role in educating a diverse community about the latest new techniques, spurring further progress.
License Creative Commons BY 3.0 DE
Markus Bläser, Valentine Kabanets, Jacobo Torán, and Christopher Umans
Dagstuhl-Seminar Series
- 16411: "Algebraic Methods in Computational Complexity" (2016)
- 14391: "Algebra in Computational Complexity" (2014)
- 12421: "Algebraic and Combinatorial Methods in Computational Complexity" (2012)
- 09421: "Algebraic Methods in Computational Complexity" (2009)
- 07411: "Algebraic Methods in Computational Complexity " (2007)
- 04421: "Algebraic Methods in Computational Complexity" (2004)
- 02421: "Algebraic Methods in Quantum and Classical Models of Computation" (2002)
Classification
- Data Structures / Algorithms / Complexity
Keywords
- Computational complexity
- Algebra
- (de)randomization
- Circuits
- Coding
Buchausstellung im Erdgeschoss der Bibliothek
(nur in der Veranstaltungswoche).
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).
Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.
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.
Seminar Homepage : Letzte Änderung 24.02.2019, 00:18 Uhr