https://www.dagstuhl.de/09421
October 11 – 16 , 2009, Dagstuhl Seminar 09421
Algebraic Methods in Computational Complexity
Organizers
Manindra Agrawal (Indian Institute of Technology – Kanpur, IN)
Lance Fortnow (Northwestern University – Evanston, US)
Thomas Thierauf (Hochschule Aalen, DE)
Christopher Umans (CalTech – Pasadena, US)
For support, please contact
Documents
Dagstuhl Seminar Proceedings
List of Participants
Dagstuhl Seminar Schedule [pdf]
Summary
The seminar brought together more than 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, most of them about 40 minutes leaving ample room for discussions. We also had a much appreciated open problem session. In the following we describe the major topics in more detail.
The talks ranged over a broad assortment of subjects with the underlying theme of using algebraic techniques. It was very fruitful and has hopefully initiated new directions in research. Several participants specifically mentioned that they appreciated the particular focus on a common class of techniques (rather than end results) as a unifying theme of the workshop. We look forward to our next meeting!
Dagstuhl Seminar Series
- 22371: "Algebraic and Analytic Methods in Computational Complexity" (2022)
- 18391: "Algebraic Methods in Computational Complexity" (2018)
- 16411: "Algebraic Methods in Computational Complexity" (2016)
- 14391: "Algebra in Computational Complexity" (2014)
- 12421: "Algebraic and Combinatorial Methods in Computational Complexity" (2012)
- 07411: "Algebraic Methods in Computational Complexity " (2007)
- 04421: "Algebraic Methods in Computational Complexity" (2004)
- 02421: "Algebraic Methods in Quantum and Classical Models of Computation" (2002)
Classification
- Data Structures
- Algorithms
- Complexity
- Security
- Cryptography
- Verification
- Logic
Keywords
- Computational complexity
- Algebra
- (de-) randomization