Dagstuhl-Seminar 02421
Algebraic Methods in Quantum and Classical Models of Computation
( 13. Oct – 18. Oct, 2002 )
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/02421
Organisatoren
- Harry Buhrman (CWI - Amsterdam, NL)
- Lance Fortnow (University of Chicago, US)
- Thomas Thierauf (FH Aalen, DE)
Kontakt
In the past fifteen years, we have seen several surprising results in computational complexity based on algebraic techniques, including
- Barrington's Theorem used noncommutative groups to show that majority can be computed by bounded-width branching programs.
- Razborov and Smolensky used low-degree polynomials over small fields to give lower bounds on the size of small depth circuits.
- Toda's theorem showing that the polynomial-time hierarchy reduces to the permanent uses many algebraic properties of polynomials.
- Research in interactive proofs a rely on the structure of the zeros of low-degree polynomials.
- The work on probabilistically checkable proofs that led to hardness of approximation results in addition to building on the interactive proof work, require algebraic techniques for testing whether a function is close to a low-degree polynomial.
In the past few years there has been a surge of interest in quantum computation, a model defined using quantum mechanics. The quantum computation model is inherently algebraic as it is defined by unitary linear transformations. Indeed many of the important results on quantum computation require algebraic techniques. Shor's famous algorithm for factoring efficiently on a quantum computer relies heavily on the algebraic structure of the groups Zm and can be seen as a special case of the hidden subgroup problem for abelian groups. Also realizing that the acceptance probability for quantum decision trees can be expressed as a low-degree polynomial gives many interesting lower bounds for that model.
Consider the graph isomorphism question which is a special case of the hidden subgroup problem for general groups. It remains open whether the graph isomorphism problem has an efficient quantum algorithm. We have seen several results on the classical complexity of graph isomorphism based on the structure of the isomorphism group. For example, one can show a bounded-round proof system for graph nonisomorphism which gives strong evidence that graph isomorphism is not NP-complete. Perhaps some of the classical ideas can be used to help settle the quantum complexity of graph isomorphism.
The seminar brought together leading researchers using algebraic techniques from both the quantum computation area and those studying classical models. Combining these groups of researchers leads to a greater understanding of the computational power of both quantum and classical models of computation through new applications of algebraic techniques.
- 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]
- Eric Allender (Rutgers University - Piscataway, US) [dblp]
- Andris Ambainis (University of Waterloo, CA) [dblp]
- Klaus Ambos-Spies (Universität Heidelberg, DE) [dblp]
- Vikraman Arvind (Chennai Mathematical Institute, IN) [dblp]
- Jose Luis Balcazar (UPC - Barcelona, ES) [dblp]
- Harry Buhrman (CWI - Amsterdam, NL) [dblp]
- Mart de Graaf (CWI - Amsterdam, NL)
- 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]
- Frederic Green (Clark University - Worcester, US) [dblp]
- Ulrich Hertrampf (Universität Stuttgart, 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]
- Troy Lee (CWI - Amsterdam, NL) [dblp]
- Jack H. Lutz (Iowa State University, US)
- Pierre McKenzie (University of Montréal, CA) [dblp]
- Peter Bro Miltersen (Aarhus University, DK) [dblp]
- Ilan Newman (University of Haifa, IL) [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)
- Rainer Schuler (Universität Ulm, DE)
- Leonard J. Schulman (Caltech - Pasadena, US) [dblp]
- Robert Spalek (CWI - Amsterdam, NL)
- Frank Stephan (National University of Singapore, SG) [dblp]
- Mario Szegedy (Rutgers University - Piscataway, US) [dblp]
- 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)
- Wim van Dam (University of California - Berkeley, US) [dblp]
- Nikolay K. Vereshchagin (Moscow State University, RU) [dblp]
- Paul M. B. Vitanyi (CWI - Amsterdam, NL)
- Klaus W. Wagner (Universität Würzburg, DE)
Verwandte Seminare
- Dagstuhl-Seminar 04421: Algebraic Methods in Computational Complexity (2004-10-10 - 2004-10-15) (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)
