https://www.dagstuhl.de/21121

March 21 – 26 , 2021, Dagstuhl Seminar 21121

Computational Complexity of Discrete Problems

Organizers

Anna Gál (University of Texas – Austin, US)
Meena Mahajan (Institute of Mathematical Sciences – Chennai, IN)
Rahul Santhanam (University of Oxford, GB)
Till Tantau (Universität zu Lübeck, DE)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 11, Issue 2 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl Seminar Schedule [pdf]

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.

Summary text license
  Creative Commons BY 4.0
  Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau

Dagstuhl Seminar Series

Classification

  • Computational Complexity
  • Data Structures And Algorithms

Keywords

  • Computational complexity
  • Circuit complexity
  • Communication complexity
  • Randomness
  • Lower bounds

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.