https://www.dagstuhl.de/07411

October 7 – 12 , 2007, Dagstuhl Seminar 07411

Algebraic Methods in Computational Complexity

Organizers

Manindra Agrawal (Indian Institute of Technology – Kanpur, IN)
Harry Buhrman (CWI – Amsterdam, NL)
Lance Fortnow (Northwestern University – Evanston, US)
Thomas Thierauf (Hochschule Aalen, DE)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl's Impact: Documents available

Summary

The seminar brought together almost 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed once again the great importance of algebraic techniques for theoretical computer science. We had almost 30 talks of length between 15 and 45 minutes. This left enough room for discussions. We had an open problem session that was very much appreciated. In the following we describe the talks in more detail.

The construction of good extractors and expanders plays a crucial role in derandomization. Chris Umans explained how to construct highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree, essentially optimal. The construction is based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy (FOCS `05). Anup Rao considered the model that the source, a family of distributions, gives a random point from some unknown low dimensional affine subspace with a low-weight basis. This model generalizes the well studied model of bit-fixing sources. He showed how to construct new extractors for this model that have exponentially small error, a parameter that is important for applications in cryptography.

Derandomization is strongly related to proving lower bounds. In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP: if one cannot derandomize BPP, then E needs exponential size circuits. Ronen Shaltiel considered the Artur-Merlin class AM instead of BPP. He showed uniform hardness vs.\ randomness tradeoffs for AM that are near-optimal for the full range of possible hardness assumptions.

As is evident from the list above, the talks ranged a wide area of subjects with the underlying of using algebraic techniques. It was very fruitful and has hopefully initiated new directions in research. We look forward to our next meeting!

Dagstuhl Seminar Series

Classification

  • Data Structures / Algorithms / Complexity
  • Security / Cryptography

Keywords

  • Computational complexity
  • Algebra
  • Quantum computing
  • (de-) randomization

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.

NSF young researcher support