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
- Amey Bhangale
- Igor Carboni Oliveira
- Amit Chakrabarti
- Sourav Chakraborty
- Arkadev Chattopadhyay
- Eshan Chattopadhyay
- Gil Cohen
- Radu Curticapean
- Yogesh Dahiya
- Susanna de Rezende
- Yuval Filmus
- Anna Gál
- Sumegha Garg
- Alexander Golovnev
- Mika Göös
- Prahladh Harsha
- Johan Hastad
- Shuichi Hirahara
- Kaave Hosseini
- Rahul Ilango
- Valentine Kabanets
- Gillat Kol
- Antonina Kolokolova
- Swastik Kopparty
- Oliver Korten
- Michal Koucký
- Sophie Laplante
- Nutan Limaye
- Siqi Liu
- Zhenjian Lu
- Meena Mahajan
- Ian Mertz
- Jakob Nordström
- Pavel Pudlák
- Rüdiger Reischuk
- Hanlin Ren
- Robert Robere
- Noga Ron-Zewi
- Michael E. Saks
- Rahul Santhanam
- Makrand Sinha
- Amnon Ta-Shma
- Avishay Tal
- Roei Tell
- Thomas Thierauf
- Jacobo Torán
- Rachel Zhang
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
