Dagstuhl Seminar 04421
Algebraic Methods in Computational Complexity
( Oct 10 – Oct 15, 2004 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/04421
Organizers
- Harry Buhrman (CWI - Amsterdam, NL)
- Lance Fortnow (University of Chicago, US)
- Thomas Thierauf (FH Aalen, DE)
Contact
Impacts
- Completeness in the Boolean hierarchy : exact-four-colorability, minimal graph uncolorability, and exact domatic number problems : a survey : article presented at the Dagstuhl Seminar 04421 : S. 551-578 - Riege, Tobias; Rothe, Jörg - Graz : J.UCS, 2006 - (J.UCS : Journal of universal computer science : 12. 2006, 5, S. 551-578).
- Incremental branching programs : article : S. 159-184 (based on Dagstuhl Seminars 04141, 04421, 06111, 07411 - Gal, Anna; Koucky, Michal; MacKenzie, Pierre - Berlin : Springer, 2008 - (Theory of computing systems : 43. 2008, 2 : S. 159-184). DOI: 10.1007/s00224-007-9049-y.
- The complexity of membership problems for circuits over sets of natural numbers : article : S. 211-244 - McKenzie, Pierre; Wagner, Klaus W. - Boston : Birkhäuser, 2007 - (Computational complexity : 16. 2007, 3 : S. 211-244). DOI: 10.1007/s00037-007-0229-6.
The seminar brought together 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 saw a series of presentations by Andris Ambainis, Robert Spalek and Mario Szegedy. Ambainis described his improved method for showing lower bounds for quantum algorithms that provably beats the degree method. Spalek talked about his work with Szegedy showing that Ambainis techniques as well as different tools developed by Zhang, Laplante and Magniez, and Barnum, Saks and Szegedy all gave the same bounds. Szegedy, in his presentation, called this measure the div complexity and showed that the size of a Boolean formula computing a function f is at least the square of the div complexity of f . Further talks on quantum complexity considered lower bounds for formula size (Scott Aaronson), finite groups (Steve Fenner), and adversary bounds (Robert Spalek).
Discussions between Laplante, Lee and Szegedy at the workshop led to the recent announcement of even a stronger lower bound for Boolean formula complexity using a stronger version of div complexity called maxPI.
Manindra Agrawal presented recent work of his students Neeraj Kayal and Nitin Saxena (the trio that showed a polynomial-time algorithm for primality testing) on rings given by a matrix describing the actions on the base elements. They show a randomized reduction from graph isomorphism to ring isomorphism and from factoring to # RI , counting the number of ring isomorphisms. They also show a polynomial-time algorithm for determining if there are any non-trivial automorphisms of a ring and that # RI is computable with an oracle for AM ∩ coAM . Agrawal conjectured that # RI is computable in polynomial time, a conjecture that would imply factoring and graph isomorphism have efficient algorithms.
In addition to Agrawal's presentation on ring isomorphism, we had a wide-range of talks on classical complexity. Lance Fortnow, building on work of Shaltiel and Umans, characterized the interesting question whether EXP is contained in NP with logarithmically bounded advice. Judy Goldsmith showed that the dominance problem for user preferences is PSPACE complete. Various hypothesis in complexity theory were compared by John Hitchcock. Jörg Rothe located the Exact-Four-Colorability problem in the boolean hierarchy. Several probabilistic time classes were separated by Rahul Santhanam. Leen Torenvliet considered autoreducible sets and Falk Unger presented some new results on sparse self-reducible sets. Talks on circuit complexity were given by Anna Gal, Ryan O'Donnell and Denis Therien.
Troy Lee considered the symmetry of information in Kolmogorov complexity. Klaus Ambos-Spies presented algorithmic and resource-bounded genericity concepts. Tolerant property tester were investigated by Eldar Fischer, and automatic structures by Frank Stephan. Markus Maucher presented a very interesting relationship between the entropy of random source and the running time of (randomized) quicksort, where the random source is used for the choice of the pivot element. Rüdiger Reischuk considered string compression based on context-free grammars: the problem to determine the minimal size of a grammar that produces precisely one given string x was shown to be NP-hard for alphabets of larger size.
- Scott Aaronson (Institute of Advanced Study - Princeton, US) [dblp]
- Farid Ablayev (Kazan State University, RU) [dblp]
- Manindra Agrawal (Indian Institute of Technology - Kanpur, IN) [dblp]
- Andris Ambainis (University of Waterloo, CA) [dblp]
- Klaus Ambos-Spies (Universität Heidelberg, DE) [dblp]
- Jose Luis Balcazar (UPC - Barcelona, ES) [dblp]
- Harry Buhrman (CWI - Amsterdam, NL) [dblp]
- Stephen A. Fenner (University of South Carolina - Columbia, US) [dblp]
- Eldar Fischer (Technion - Haifa, IL)
- Lance Fortnow (University of Chicago, US) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- William Gasarch (University of Maryland - College Park, US) [dblp]
- Judy Goldsmith (University of Kentucky - Lexington, US) [dblp]
- Frederic Green (Clark University - Worcester, US) [dblp]
- John Hitchcock (University of Wyoming - Laramie, US)
- Thanh Minh Hoang (Universität Ulm, DE)
- Steve Homer (Boston University, US)
- Peter Hoyer (University of Calgary, CA) [dblp]
- Airat Khasianov (Universität Bonn, DE)
- Hartmut Klauck (Universität Frankfurt, DE) [dblp]
- Sophie Laplante (Université Paris Sud, FR) [dblp]
- Troy Lee (CWI - Amsterdam, NL) [dblp]
- Markus Maucher (Universität Ulm, DE)
- Pierre McKenzie (University of Montréal, CA) [dblp]
- Jochen Messner (Universität Ulm, DE) [dblp]
- Ilan Newman (University of Haifa, IL) [dblp]
- Ryan O'Donnell (Microsoft Research - Redmond, US) [dblp]
- Kenneth Regan (SUNY - Buffalo, US)
- Rüdiger Reischuk (Universität Lübeck, DE) [dblp]
- John D. Rogers (DePaul University - Chicago, US)
- Hein Röhrig (CWI - Amsterdam, NL)
- Jörg Rothe (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- Rahul Santhanam (University of Chicago, US) [dblp]
- Martin Sauerhoff (TU Dortmund, DE)
- Uwe Schöning (Universität Ulm, DE) [dblp]
- Rainer Schuler (Universität Ulm, DE)
- Robert Spalek (CWI - Amsterdam, NL)
- Frank Stephan (National University of Singapore, SG) [dblp]
- Mario Szegedy (Rutgers University - Piscataway, US) [dblp]
- Pascal Tesson (McGill University - Montreal, CA)
- Denis Therien (McGill University - Montreal, CA) [dblp]
- Thomas Thierauf (FH Aalen, DE) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Leen Torenvliet (University of Amsterdam, NL)
- Falk Unger (CWI - Amsterdam, NL)
- Nikolay K. Vereshchagin (Moscow State University, RU) [dblp]
- Klaus W. Wagner (Universität Würzburg, DE)
- Stephanie Wehner (CWI - Amsterdam, NL) [dblp]
Related Seminars
- Dagstuhl Seminar 02421: Algebraic Methods in Quantum and Classical Models of Computation (2002-10-13 - 2002-10-18) (Details)
- Dagstuhl Seminar 07411: Algebraic Methods in Computational Complexity (2007-10-07 - 2007-10-12) (Details)
- Dagstuhl Seminar 09421: Algebraic Methods in Computational Complexity (2009-10-11 - 2009-10-16) (Details)
- Dagstuhl Seminar 12421: Algebraic and Combinatorial Methods in Computational Complexity (2012-10-14 - 2012-10-19) (Details)
- Dagstuhl Seminar 14391: Algebra in Computational Complexity (2014-09-21 - 2014-09-26) (Details)
- Dagstuhl Seminar 16411: Algebraic Methods in Computational Complexity (2016-10-09 - 2016-10-14) (Details)
- Dagstuhl Seminar 18391: Algebraic Methods in Computational Complexity (2018-09-23 - 2018-09-28) (Details)
- Dagstuhl Seminar 22371: Algebraic and Analytic Methods in Computational Complexity (2022-09-11 - 2022-09-16) (Details)
- Dagstuhl Seminar 24381: Algebraic and Analytic Methods in Computational Complexity (2024-09-15 - 2024-09-20) (Details)
