Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Innerhalb dieser Seite:
Externe Seiten:
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp

Dagstuhl-Seminar 24381

Algebraic and Analytic Methods in Computational Complexity

( 15. Sep – 20. Sep, 2024 )

Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:




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 algebraic theme continues to play a central role in some of the most exciting recent progress in computational complexity in areas like circuit complexity, polynomial identity testing, pseudorandomness and derandomization or error correcting codes.

Beside algebraic methods, analytic methods like Fourier analysis have been used for quite some time in theoretical computer science. These methods have been used recently in some breakthrough results in complexity theory in areas like hardness of approximation, quantum computation and scaling algorithms.

A new theme that has gained importance in the last years is the area of meta-complexity, that is, the complexity of computational problems that are themselves problems about the complexity of computation. Meta-complexity provides a link between a variety of important areas like circuit complexity, proof complexity, cryptography, and learning theory.

These new directions will be in the focus of the Dagstuhl Seminar and reflect the developments in the field since the previous Dagstuhl Seminar 22371. 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 we hope that this seminar will contribute in educating a diverse community about the latest new techniques.

Copyright Markus Bläser, Shubhangi Saraf, Ronen Shaltiel, and Jacobo Torán

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)

  • Computational Complexity

  • computational complexity
  • algebra
  • (de-)randomization
  • circuits
  • coding theory