Dagstuhl-Seminar 27371
Algebraic and Combinatorial Methods in Computational Complexity
( 12. Sep – 17. Sep, 2027 )
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/27371
Organisatoren
- Markus Bläser (Universität des Saarlandes - Saarbrücken, DE)
- Nutan Limaye (IT University of Copenhagen, DK)
- Shubhangi Saraf (University of Toronto, CA)
- Ronen Shaltiel (University of Haifa, IL)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Christina Schwarz (für administrative Fragen)
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.
This Dagstuhl Seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic and combinatorial methods in a variety of settings in Computational Complexity. 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 recent progress and the latest new techniques. The seminar should also provide an opportunity to reflect on the recent exciting developments since the previous Dagstuhl Seminar 24381.
While the focus on "algebraic techniques" is used as a unifying theme, we also want to explicitly include recent exciting progress in the field that builds on combinatorial techniques. For example, an impressive set of recent results in catalytic space computation uses algebraic and combinatorial techniques to improve the space complexity of fundamental problems such as the tree evaluation problem and the time-versus-space question. Another example is the recent pseudo-deterministic polynomial time algorithms for finding primes. This algorithm builds on (conditional) hardness vs. randomness tradeoffs and combines combinatorial and algebraic techniques. The new breakthrough results on lower bounds for locally decodable codes and locally correctable codes use recent developments in graph theory as well as techniques developed for semi-random CSP refutations and are another great example of algebraic and combinatorial techniques coming together. Finally, one of the main tools of geometric complexity theory is representation theory, which is closely related to combinatorics.
By bringing together researchers working at the interface of algebraic and combinatorial methods, this seminar aims to foster new collaborations and exchange of ideas. The continued interplay between algebraic structure and combinatorial insight has led to some of the most exciting recent developments in Computational Complexity, and we expect this seminar to further accelerate progress. We hope it will serve as a platform for highlighting emerging techniques and identifying promising directions for future research.
Creative Commons BY 4.0
Markus Bläser, Nutan Limaye, Shubhangi Saraf, and Ronen Shaltiel
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)
- 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
- Computational Complexity
Schlagworte
- computational complexity
- algebra
- derandomization
- error correcting codes
- circuits
