Dagstuhl-Seminar 25111
Computational Complexity of Discrete Problems
( 09. Mar – 14. Mar, 2025 )
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)
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
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
