Dagstuhl-Seminar 25111
Computational Complexity of Discrete Problems
( 09. Mar – 14. Mar, 2025 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/25111
Organisatoren
- Swastik Kopparty (University of Toronto, CA)
- Meena Mahajan (The Institute of Mathematical Sciences & HBNI - Chennai, IN)
- Rahul Santhanam (University of Oxford, GB)
- Till Tantau (Universität zu Lübeck, DE)
Kontakt
- Andreas Dolzmann (für wissenschaftliche Fragen)
- Simone Schilke (für administrative Fragen)
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)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Gemeinsame Dokumente
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Computational complexity studies the amount of resources (such as time, space, randomness, communication, or parallelism) necessary to solve discrete problems – a crucial task both in theoretical and practical applications. Despite a long line of research, for many practical problems it is not known if they can be solved efficiently. Here, “efficiently” can refer to polynomial-time algorithms, whose existence is not known for problems like Satisfiability or Factoring. For the large data sets arising for instance in machine learning, already cubic or even quadratic time may be too large, but may be unavoidable as research on fine-grained complexity indicates. The ongoing research on such fundamental problems has a recurring theme: The difficulty of proving lower bounds. Indeed, many of the great open problems of theoretical computer science are, in essence, open lower bound problems.
In this Dagstuhl Seminar, we will address several of the arising questions in the context of circuit and formula sizes, meta-complexity, proof complexity, fine-grained complexity, communication complexity, and classical computational complexity. In each area, powerful tools for proving lower and upper bounds are known, but particularly interesting and powerful results often arise from establishing connections between the fields. By bringing together a diverse group of leading experts and promising young researchers in these areas, the seminar will be an ideal place to discover new, further connections.
The bulk of the seminar will be taken up by talks and discussions. The topics will depend on and be driven by the participants, who will share their current research interests in talks, open problem sessions, and smaller group research.
Creative Commons BY 4.0
Swastik Kopparty, Meena Mahajan, Rahul Santhanam, and Till Tantau
Please log in to DOOR to see more details.
- Olaf Beyersdorff (Friedrich-Schiller-Universität Jena, DE) [dblp]
- Amey Bhangale (University of California - Riverside, US)
- Igor Carboni Oliveira (University of Warwick - Coventry, GB) [dblp]
- Amit Chakrabarti (Dartmouth College - Hanover, US) [dblp]
- Sourav Chakraborty (Indian Statistical Institute - Kolkata, 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]
- Yogesh Dahiya (The Institute of Mathematical Sciences - Chennai, IN)
- Susanna de Rezende (Lund University, SE) [dblp]
- Yuval Filmus (Technion - Haifa, IL) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Sumegha Garg (Rutgers University - New Brunswick, US)
- Alexander Golovnev (Georgetown University - Washington, DC, US) [dblp]
- Mika Göös (EPFL Lausanne, CH) [dblp]
- Prahladh Harsha (TIFR - Mumbai, IN) [dblp]
- Johan Hastad (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Shuichi Hirahara (National Institute of Informatics - Tokyo, JP) [dblp]
- Kaave Hosseini (University of Rochester, US)
- Rahul Ilango (MIT - Cambridge, US) [dblp]
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Gillat Kol (Princeton University, US) [dblp]
- Antonina Kolokolova (Memorial University of Newfoundland - St. John's, CA) [dblp]
- Swastik Kopparty (University of Toronto, CA) [dblp]
- Oliver Korten (Columbia University - New York, US)
- Michal Koucký (Charles University - Prague, CZ) [dblp]
- Sophie Laplante (Université Paris Cité, FR) [dblp]
- Nutan Limaye (IT University of Copenhagen, DK) [dblp]
- Siqi Liu (Institute for Advanced Study - Princeton, US)
- Zhenjian Lu (University of Warwick - Coventry, GB) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences & HBNI - Chennai, IN) [dblp]
- Ian Mertz (Charles University - Prague, CZ)
- Jakob Nordström (University of Copenhagen, DK & Lund University, SE) [dblp]
- Pavel Pudlák (The Czech Academy of Sciences - Prague, CZ) [dblp]
- Rüdiger Reischuk (Universität zu Lübeck, DE) [dblp]
- Hanlin Ren (University of Oxford, GB) [dblp]
- Robert Robere (McGill University - Montréal, CA) [dblp]
- Noga Ron-Zewi (University of Haifa, IL) [dblp]
- Michael E. Saks (Rutgers University - Piscataway, US) [dblp]
- Rahul Santhanam (University of Oxford, GB) [dblp]
- Makrand Sinha (University of Illinois - Urbana-Champaign, US)
- Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
- Avishay Tal (University of California - Berkeley, US) [dblp]
- Roei Tell (University of Toronto, CA) [dblp]
- Thomas Thierauf (Hochschule Aalen, DE) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Rachel Zhang (MIT - Cambridge, US)
Verwandte Seminare
- Dagstuhl-Seminar 9235: Complexity and Realization of Boolean Functions (1992-08-24 - 1992-08-28) (Details)
- Dagstuhl-Seminar 9711: Complexity of Boolean Functions (1997-03-10 - 1997-03-14) (Details)
- Dagstuhl-Seminar 99441: Complexity of Boolean Functions (1999-10-31 - 1999-11-05) (Details)
- Dagstuhl-Seminar 02121: Complexity of Boolean Functions (2002-03-17 - 2002-03-22) (Details)
- Dagstuhl-Seminar 04141: Complexity of Boolean Functions (2004-03-28 - 2004-04-02) (Details)
- Dagstuhl-Seminar 06111: Complexity of Boolean Functions (2006-03-12 - 2006-03-17) (Details)
- Dagstuhl-Seminar 08381: Computational Complexity of Discrete Problems (2008-09-14 - 2008-09-19) (Details)
- Dagstuhl-Seminar 11121: Computational Complexity of Discrete Problems (2011-03-20 - 2011-03-25) (Details)
- Dagstuhl-Seminar 14121: Computational Complexity of Discrete Problems (2014-03-16 - 2014-03-21) (Details)
- Dagstuhl-Seminar 17121: Computational Complexity of Discrete Problems (2017-03-19 - 2017-03-24) (Details)
- Dagstuhl-Seminar 19121: Computational Complexity of Discrete Problems (2019-03-17 - 2019-03-22) (Details)
- Dagstuhl-Seminar 21121: Computational Complexity of Discrete Problems (2021-03-21 - 2021-03-26) (Details)
- Dagstuhl-Seminar 23111: Computational Complexity of Discrete Problems (2023-03-12 - 2023-03-17) (Details)
Klassifikation
- Computational Complexity
- Data Structures and Algorithms
- Discrete Mathematics
Schlagworte
- computational complexity
- circuit complexity
- communication complexity
- lower bounds
- randomness
