Dagstuhl Seminar 24381
Algebraic and Analytic Methods in Computational Complexity
( Sep 15 – Sep 20, 2024 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/24381
Organizers
- Markus Bläser (Universität des Saarlandes - Saarbrücken, DE)
- Shubhangi Saraf (University of Toronto, CA)
- Ronen Shaltiel (University of Haifa, IL)
- Jacobo Torán (Universität Ulm, DE)
Contact
- Michael Gerke (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Dagstuhl Reports
As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.
- Upload (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
- Upload (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 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.
Creative Commons BY 4.0
Markus Bläser, Shubhangi Saraf, Ronen Shaltiel, and Jacobo Torán
- Robert Andrews (University of Waterloo, CA) [dblp]
- Vikraman Arvind (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Vishwas Bhargava (University of Waterloo, CA) [dblp]
- Markus Bläser (Universität des Saarlandes - Saarbrücken, DE) [dblp]
- Andrej Bogdanov (University of Ottawa, CA) [dblp]
- Harry Buhrman (University of Amsterdam, NL) [dblp]
- Peter Bürgisser (TU Berlin, DE) [dblp]
- Igor Carboni Oliveira (University of Warwick - Coventry, GB) [dblp]
- Prerona Chatterjee (NISER - Bhubaneswar, IN) [dblp]
- Arkadev Chattopadhyay (TIFR - Mumbai, IN) [dblp]
- Eshan Chattopadhyay (Cornell University - Ithaca, US) [dblp]
- Gil Cohen (Tel Aviv University, IL) [dblp]
- Radu Curticapean (Universität Regensburg, DE) [dblp]
- Dean Doron (Ben Gurion University - Beer Sheva, IL) [dblp]
- Klim Efremenko (Ben Gurion University - Beer Sheva, IL) [dblp]
- Michael A. Forbes (University of Illinois - Urbana-Champaign, US) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Rohit Gurjar (Indian Institute of Technology Bombay - Mumbai, IN) [dblp]
- Shuichi Hirahara (National Institute of Informatics - Tokyo, JP) [dblp]
- William Hoza (University of Chicago, US) [dblp]
- Christian Ikenmeyer (University of Warwick - Coventry, GB) [dblp]
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Neeraj Kayal (Microsoft Research India - Bangalore, IN) [dblp]
- Pascal Koiran (ENS - Lyon, FR) [dblp]
- Antonina Kolokolova (Memorial University of Newfoundland - St. John's, CA) [dblp]
- Michal Koucký (Charles University - Prague, CZ) [dblp]
- Donald Kougang Yombi (AIMS Rwanda - Kigali, RW) [dblp]
- Mrinal Kumar (TIFR Mumbai, IN) [dblp]
- Nutan Limaye (IT University of Copenhagen, DK) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Or Meir (University of Haifa, IL) [dblp]
- Rafael Mendes de Oliveira (University of Waterloo, CA) [dblp]
- Noga Ron-Zewi (University of Haifa, IL) [dblp]
- Kilian Rothmund (Hochschule Aalen, DE)
- Rahul Santhanam (University of Oxford, GB) [dblp]
- Ramprasad Saptharishi (TIFR Mumbai, IN) [dblp]
- Shubhangi Saraf (University of Toronto, CA) [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]
- Jad Silbak (Northeastern University - Boston, US) [dblp]
- Srikanth Srinivasan (University of Copenhagen, DK) [dblp]
- Sathyawageeswar Subramanian (University of Cambridge, GB) [dblp]
- Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
- Sébastien Tavenas (University Savoie Mont Blanc - Le Bourget-du-Lac, FR) [dblp]
- Roei Tell (University of Toronto, CA) [dblp]
- Thomas Thierauf (Hochschule Aalen, DE) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Christopher Umans (California Institute of Technology - Pasadena, US) [dblp]
- Jeroen Zuiddam (University of Amsterdam, NL) [dblp]
Related Seminars
- 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)
Classification
- Computational Complexity
Keywords
- computational complexity
- algebra
- (de-)randomization
- circuits
- coding theory
