TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 21121

Computational Complexity of Discrete Problems

( Mar 21 – Mar 26, 2021 )


Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/21121

Organizers

Contact


Schedule

Motivation

Computational complexity studies the amount of resources (such as time, space, randomness, or communication) that are necessary to solve computational problems in various models of computation. Finding efficient algorithms for solving computational tasks is crucial for practical applications. Despite a long line of research, for many problems that arise in practice it is not known if they can be solved efficiently – in particular, in polynomial time. Beside questions about the existence of polynomial time algorithms for problems like Satisfiability or Factoring, where the best known algorithms run in exponential time, there is a huge class of practical problems where algorithms with polynomial running time (such as cubic or even quadratic time) are known, but it would be important to establish whether these running times are best possible, to what extent they can be improved, and whether parallel algorithms allow improvements of the runtime.

These fundamental questions motivate developments in various areas from algorithm design to circuit complexity, communication complexity and proof complexity. During this Dagstuhl Seminar, we plan to discuss some of the most exciting recent developments in those areas related to computational complexity.

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. The list of topics will include subjects such as new lower bounds on formula size and circuit size, complexity measures of Boolean functions, the algorithmic method for proving lower bounds, fixed parameter tractability and hardness magnification, communication complexity and lifting techniques, as well as proof complexity.

The seminar is a continuation of the series of Dagstuhl Seminars entitled “Computational Complexity of Discrete Problems”. It will build on the long experience and retain the features that have made the series strong in the past, while also capitalizing on new and exciting developments in the area such as the proof of the Sensitivity Conjecture, new lower bounds and results on matrix rigidity via the algorithmic method, and the remarkable success of lifting techniques in translating lower bounds from query complexity to communication complexity and from proof complexity to circuit complexity.

Copyright Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau

Summary

Computational complexity studies the amount of resources (such as time, space, randomness, or communication) that are necessary to solve computational problems in various models of computation. Finding efficient algorithms for solving computational tasks is crucial for practical applications. Despite a long line of research, for many problems that arise in practice it is not known if they can be solved efficiently – in particular, in polynomial time. Beside questions about the existence of polynomial time algorithms for problems like Satisfiability or Factoring, where the best known algorithms run in exponential time, there is a huge class of practical problems where algorithms with polynomial running time (such as cubic or even quadratic time) are known, but it would be important to establish whether these running times are best possible, to what extent they can be improved, and whether parallel algorithms allow improvements of the runtime.

These fundamental questions motivate developments in various areas from algorithm design to circuit complexity, communication complexity and proof complexity. During this Dagstuhl Seminar 21121, some of the most exciting recent developments in those areas related to computational complexity were presented in a series of talks. The seminar was the most recent one in the series of Dagstuhl Seminars entitled "Computational Complexity of Discrete Problems" - seminars 19121, 17121, 14121, 11121.

Owing to the pandemic and associated travel restrictions, the seminar was held in a purely online format. With 52 researchers from across the world participating in the event, resident in time zones ranging from Japan to California, the window for common acceptable time slots was small. We decided to have a two-hour time slot each day for technical sessions, followed by an additional hour or more each day for social interactions. The Webex platform was used for technical sessions, and gather.town additionally for some of the social interactions. Despite the challenges of making the online event interesting given the ubiquitous screen-time fatigue, the meetings saw high participation level (between at least 80% and typically over 90% participation on all days) and were highly interactive - primarily due to the excellent nature of the given talks.

The seminar started with the creation of a "graph of interests" (using a Miro whiteboard), enabling participants to discover shared research interests with other participants. Following this, during the week, there were 20 research talks, coming from a range of topics including lower bounds on formula size and circuit size, complexity measures of Boolean functions, the algorithmic method for proving lower bounds, fixed parameter tractability and hardness magnification, communication complexity and lifting techniques, as well as proof complexity. Some specific results presented include:

  • An improved lower bound, after many years, on the number of hyperplanes needed to slice all edges of the Boolean hypercube.
  • A lower bound for monotone arithmetic circuit size using techniques from communication complexity.
  • A new potential technique for de Morgan formula lower bounds.
  • More refined notions of unambiguous certificate complexity and block sensitivity, with a separation that lifts to communication complexity.

The titles and abstracts of all the talks appear later in this report.

In addition, there was a rump session with short talks by Amit Chakrabarti, Amit Sinhababu, and Prahladh Harsha.

On the social interactions front, in the designated coffee slots there were some meet-random-people-in-a-break-out sessions. The traditional Wednesday hike was replaced by a "virtual hike" using Google Earth imagery, that went over one of the shorter hike trails near Schloss Dagstuhl and then virtually visited some participants' institutes. The "wine-cheese-music party" became an online party on gather.town following the Schloss Dagstuhl map, and included music, games, and a commentary on the hardness of travelling.

The organizers, Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau, thank all participants for the many contributions they made. We would also like to especially thank the Dagstuhl staff for their cooperation in the current challenging circumstances, their encouragement for going ahead with an online event, and their unstinted help with organizational matters. We would also like to thank Max Bannach for his invaluable help assembling and preparing this report.

Copyright Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau

Participants
Remote:
  • Eric Allender (Rutgers University - Piscataway, US) [dblp]
  • Max Bannach (Universität zu Lübeck, DE) [dblp]
  • Olaf Beyersdorff (Universität Jena, DE) [dblp]
  • Harry Buhrman (CWI - Amsterdam, NL) [dblp]
  • 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]
  • Lijie Chen (MIT - Cambridge, US) [dblp]
  • Anindya De (University of Pennsylvania - Philadelphia, US) [dblp]
  • Yuval Filmus (Technion - Haifa, IL) [dblp]
  • Lance Fortnow (Illinois Institute of Technology, US) [dblp]
  • Anna Gál (University of Texas - Austin, US) [dblp]
  • Alexander Golovnev (Georgetown University - Washington, DC, US) [dblp]
  • Mika Göös (EPFL Lausanne, CH) [dblp]
  • Rohit Gurjar (Indian Institute of Technology - Mumbai, IN) [dblp]
  • Kristoffer Arnsfelt Hansen (Aarhus University, DK) [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]
  • Rahul Ilango (MIT - Cambridge, US)
  • Stacey Jeffery (CWI - Amsterdam, NL) [dblp]
  • Gillat Kol (Princeton University, US) [dblp]
  • Swastik Kopparty (Rutgers University - Piscataway, US) [dblp]
  • Michal Koucký (Charles University - Prague, CZ) [dblp]
  • Alexander S. Kulikov (Steklov Institute - St. Petersburg, RU) [dblp]
  • Sophie Laplante (University Paris Diderot, FR) [dblp]
  • Nutan Limaye (Indian Institute of Technology - Mumbai, IN) [dblp]
  • Meena Mahajan (Institute of Mathematical Sciences - Chennai, IN) [dblp]
  • Ian Mertz (University of Toronto, CA)
  • Jakob Nordström (University of Copenhagen, DK & Lund University, SE) [dblp]
  • Ramamohan Paturi (University of California - San Diego, US) [dblp]
  • Toniann Pitassi (University of Toronto, CA) [dblp]
  • Pavel Pudlák (The Czech Academy of Sciences - Prague, CZ) [dblp]
  • Oded Regev (New York University, US) [dblp]
  • Rüdiger Reischuk (Universität zu Lübeck, DE) [dblp]
  • Robert Robere (McGill University - Montreal, CA) [dblp]
  • Michael E. Saks (Rutgers University - Piscataway, US) [dblp]
  • Rahul Santhanam (University of Oxford, GB) [dblp]
  • Shubhangi Saraf (Rutgers University - Piscataway, US) [dblp]
  • Amit Sinhababu (Hochschule Aalen, DE)
  • Srikanth Srinivasan (Aarhus University, DK) [dblp]
  • Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
  • Li-Yang Tan (Stanford University, US) [dblp]
  • Till Tantau (Universität zu Lübeck, DE) [dblp]
  • Thomas Thierauf (Hochschule Aalen, DE) [dblp]
  • Jacobo Torán (Universität Ulm, DE) [dblp]
  • Virginia Vassilevska Williams (MIT - Cambridge, US) [dblp]
  • Ben Lee Volk (University of Texas - Austin, US) [dblp]
  • Omri Weinstein (Columbia University - New York, US) [dblp]
  • Ryan Williams (MIT - Cambridge, US) [dblp]
  • Amir Yehudayoff (Technion - Haifa, IL) [dblp]

Related Seminars
  • 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 23111: Computational Complexity of Discrete Problems (2023-03-12 - 2023-03-17) (Details)

Classification
  • Computational Complexity
  • Data Structures and Algorithms

Keywords
  • computational complexity
  • circuit complexity
  • communication complexity
  • randomness
  • lower bounds