Dagstuhl-Seminar 22371
Algebraic and Analytic Methods in Computational Complexity
( 11. Sep – 16. Sep, 2022 )
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/22371
Organisatoren
- Markus Bläser (Universität des Saarlandes - Saarbrücken, DE)
- Valentine Kabanets (Simon Fraser University - Burnaby, CA)
- Ronen Shaltiel (University of Haifa, IL)
- Jacobo Torán (Universität Ulm, DE)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Christina Schwarz (für administrative Fragen)
Gemeinsame Dokumente
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
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.
Beside algebraic methods, analytic methods have been used for quite some time in theoretical computer science. Very recently, Fourier analysis was essential for proving a variant of the famous Unique Games Conjecture, the so-called 2-2 Conjecture.
Analytic methods can also be used to solve algebraic problems. Garg et al. use analytic scaling algorithms to solve problems from algebra, so-called orbit closure problems, by using geometric invariant theory to establish the link. Central problems, like the tensor border rank or non-commutative identity testing, can be written as such an orbit closure problem.
These new directions will be in the focus of the Dagstuhl Seminar and reflect the developments in the field since the previous Dagstuhl Seminar 18391. Taking the recent exciting developments outlined above into account, we also include analytic methods this time.
This Dagstuhl Seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic and analytic 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.
Creative Commons BY 4.0
Markus Bläser, Valentine Kabanets, Ronen Shaltiel, and Jacobo Torán
- Eric Allender (Rutgers University - Piscataway, US) [dblp]
- Markus Bläser (Universität des Saarlandes - Saarbrücken, DE) [dblp]
- Andrej Bogdanov (The Chinese University of Hong Kong, HK) [dblp]
- Peter Bürgisser (TU Berlin, DE) [dblp]
- Prerona Chatterjee (The Czech Academy of Sciences - Prague, CZ)
- Arkadev Chattopadhyay (TIFR - Mumbai, IN) [dblp]
- Gil Cohen (Tel Aviv University, IL) [dblp]
- Julian Dörfler (Universität des Saarlandes - Saarbrücken, DE)
- Stephen A. Fenner (University of South Carolina - Columbia, US) [dblp]
- Michael A. Forbes (University of Illinois - Urbana-Champaign, US) [dblp]
- Lance Fortnow (Illinois Institute of Technology, US) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Frederic Green (Clark University - Worcester, US) [dblp]
- Rohit Gurjar (Indian Institute of Technology - Mumbai, IN) [dblp]
- William Hoza (University of California - Berkeley, US) [dblp]
- Christian Ikenmeyer (University of Liverpool, GB) [dblp]
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Pascal Koiran (ENS - Lyon, FR) [dblp]
- Antonina Kolokolova (University of Newfoundland, CA) [dblp]
- Michal Koucký (Charles University - Prague, CZ) [dblp]
- Sophie Laplante (University Paris Diderot, FR) [dblp]
- Nutan Limaye (IT University of Copenhagen, DK) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Rafael Mendes de Oliveira (University of Waterloo, CA) [dblp]
- Ryan O'Donnell (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Natacha Portier (ENS - Lyon, FR) [dblp]
- Noga Ron-Zewi (University of Haifa, IL) [dblp]
- Rahul Santhanam (University of Oxford, GB) [dblp]
- Nitin Saxena (Indian Institute of Technology Kanpur, IN) [dblp]
- Rocco Servedio (Columbia University - New York, US) [dblp]
- Ronen Shaltiel (University of Haifa, IL) [dblp]
- Amir Shpilka (Tel Aviv University, IL) [dblp]
- Srikanth Srinivasan (Aarhus University, DK) [dblp]
- Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Christopher Umans (California Institute of Technology - Pasadena, US) [dblp]
- Mary Wootters (Stanford University, US) [dblp]
- David Zuckerman (University of Texas - Austin, US) [dblp]
- Jeroen Zuiddam (University of 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 16411: Algebraic Methods in Computational Complexity (2016-10-09 - 2016-10-14) (Details)
- Dagstuhl-Seminar 18391: Algebraic Methods in Computational Complexity (2018-09-23 - 2018-09-28) (Details)
Klassifikation
- Computational Complexity
Schlagworte
- computational complexity
- algebra
- (de-)randomization
- circuits
- coding
