http://www.dagstuhl.de/11121

### March 20 – 25 , 2011, Dagstuhl Seminar 11121

# Computational Complexity of Discrete Problems

## Organizers

Martin Grohe (HU Berlin, DE)

Michal Koucký (Czech Academy of Sciences – Prague, CZ)

Rüdiger Reischuk (Universität Lübeck, DE)

Dieter van Melkebeek (University of Wisconsin – Madison, US)

## For support, please contact

## Documents

Dagstuhl Report, Volume 1, Issue 3

List of Participants

Shared Documents

Dagstuhl's Impact: Documents available

Dagstuhl Seminar Schedule [pdf]

## Art exhibition opens on Monday March 21

All participants are invited to attend after dinner on 7:30 pm.

More information here .

## Summary

Computational models like Turing machines and Boolean circuits work on discrete input data. Even quantum computation and communication studied in the recent past are mainly applied to solve discrete problems. Analysing the computational complexity of such problems with respect to these models is one of the central topics in the theory of computation. Researchers try to classify algorithmic problems according to complexity measures like time and space -- both in the uniform and in the nonuniform setting. A variety of specialized computational models have been developed in order to better measure the complexity of certain classes of discrete problems.

Randomness has turned out to be another fundamental measure and added a lot of new intricate questions. Performing probabilistic choices within an algorithm one can design solution strategies for a given computational problem for which there are no obvious deterministic ones. Recently, large effort has been taken to remove randomness from probabilistic algorithms, so called derandomization. Here one tries to develop general techniques that can be applied to a wide range of discrete problems.

Information transfer is investigated according to the amount of communication necessary in different scenarios like 1-way channels or a bounded number of communication rounds. This is a basis for the design of efficient communication protocols. Furthermore, it has been observed that often ordinary computational problems given to a specific computational device can formally be analysed elegantly by concentrating on information flow aspects.

In addition, other computational processes arising in diverse areas of computer science have been studied, each with their own relevant complexity measures. Several of those investigations have evolved into substantial research areas, including:

- approximability (motivated by optimization),
- computational learning theory (motivated by artificial intelligence),
- query complexity (motivated by databases).

The analysis and relative power of basic models of computation remains a major challenge. New lower bound techniques for explicitly defined functions have brought the field a major step forward. For example, close connections have been discovered between circuit lower bounds for certain uniform complexity classes and the existence of pseudorandom generators and the possibility of efficient derandomization.

The seminar ``Computational Complexity of Discrete Problems'' has evolved out of the series of seminars entitled "Complexity of Boolean Functions," a topic that has been covered at Dagstuhl on a regular basis since the foundation of this research center. Over the years, the focus on nonuniform models has broadened to include uniform ones as well.

A salient feature of the current research in computational complexity is the interpenetration of ideas from different subareas of computational complexity and from other fields in computer science and mathematics. By organizing a generic seminar on computational complexity we have aimed to attract researchers from those various subareas and foster further fruitful interactions.

Investigating the complexity of discrete problems is one of the fundamental tasks in the theory of computation. On the one hand, new algorithmic techniques and new ways to look at a problem have led to better algorithms and protocols. On the other hand, typically more demanding is the task to prove lower bounds on the computational complexity of a concrete problem. Progress is still continuing, as seen for example in testing, derandomization and explicit constructions of combinatorial objects like extractors, that improves our knowledge considerably. Despite these significant steps forward that have been achieved in several subareas since our previous meeting three years ago, the general feeling among the participants was that we still have to work hard for many more years to get a good understanding what are the limits of efficient computation.

We like to thank the staff at Dagstuhl who -- as usual -- provided a marvellous surrounding to make this a successful meeting with ample space for undisturbed interactions between the participants.

## Dagstuhl Seminar Series

- 17121: "Computational Complexity of Discrete Problems" (2017)
- 14121: "Computational Complexity of Discrete Problems" (2014)
- 08381: "Computational Complexity of Discrete Problems" (2008)
- 06111: "Complexity of Boolean Functions " (2006)
- 04141: "Complexity of Boolean Functions" (2004)
- 02121: "Complexity of Boolean Functions" (2002)
- 99441: "Complexity of Boolean Functions" (1999)
- 9711: "Complexity of Boolean Functions" (1997)
- 9235: "Complexity and Realization of Boolean Functions" (1992)

## Classification

- Data Structures / Algorithms / Complexity

## Keywords

- Computational complexity
- Discrete problems
- Turing machines
- Circuits