Bulletin of the
European Association for Theoretical Computer Science
Computational Complexity Column


Editor, Jacobo Torán

Previous Editors:
Lance Fortnow, June 2000 - February 2004
Eric Allender, June 1997 - February 2000
Juris Hartmanis, February 1987 - February 1996

Lane Hemaspaandra edits a sister column for SIGACT News.

Please contact the editor if you have any comments on the column or suggestions for future column topics.

Complexity Links

IEEE Conference on Computational Complexity
Electronic Colloquium on Computational Complexity
Scott Aaronson's Complexity Zoo
Lance Fortnow's Web Log

Articles

 
Number 103, February, 2011, On the Notion of Bit Complexity
by Claus Diem        [PDF]   [PS]  
Number 102, October, 2010, Complexity of Non-Monotonic Logics
by Michael Thomas and Heribert Vollmer        [PDF]   [PS]  
Number 101, June, 2010, Researching the Complexity of Boolean Functions with Computers
by Kazuyuki Amano        [PDF]   [PS]  
Number 100, February, 2010, Multilinear Polynomial Modulo Composites
by Arkadev Chattopadhyay        [PDF]   [PS]  
Number 99, October, 2009, Progress in Polynomial Identity Testing
by Nitin Saxena        [PDF]   [PS]  
Number 98, June, 2009, Integer Multiplication and the Complexity of Binary Decision Diagrams
by Beate Bollig        [PDF]   [PS]  
Number 97, February, 2009, The Complexity of Planar Graph Isomorphism
by Jacobo Toran and Fabian Wagner        [PDF]   [PS]  
Number 95, June, 2008, Communication Lower Bounds Using Dual Polynomials
by Alexander A. Sherstov        [PDF]   [PS]  
Number 94, February, 2008, Kolmogorov Complexity and Games
by Nikolai Vereshchagin        [PDF]   [PS]  
Number 93, October, 2007, Quantum Computing and the Hunt for Hidden Symmetry
by Gorjan Alagic and Alexander Russel        [PDF]  
Number 91, February, 2007, Polynomial Size Log Depth Circuits: Between NC1 and AC1
by Meena Mahajan        [PDF]   [Postscript]
Number 90, October, 2006, Iterative Decoding of Low-Density Parity Check Codes
by Venkatesan Guruswami        [PDF]   [Postscript]
Number 89, June, 2006, Learning Boolean Functions under the uniform distribution via the Fourier Transform
by Johannes Köbler and Wolfgang Lindner        [PDF]   [Postscript]
Number 88, February, 2006, Bridges between Algebraic Automata Theory and Complexity Theory
by Pascal Tesson and Denis Thérien        [PDF]   [Postscript]
Number 87, October, 2005, Lower Bounds on Quantum Query Complexity
by Peter Høyer and Robert Spalek        [PDF]   [Postscript]
Number 86, June, 2005, Isomorphism Testing: Perspective and Open Problems
by V. Arvind and Jacobo Torán        [PDF]   [Postscript]
Number 85, February, 2005, A Post's Program For Complexity Theory
by Harry Buhrmann and Leen Torenvliet        [PDF]
Number 84, October , 2004, Parametrized Complexity and Subexponential Time
by Jorg Flum and Martin Grohe        [PDF]   [Postscript]
Number 83, June, 2004, Space and Width in Propositional Resolution
by Jacobo Torán        [PDF]   [Postscript]
Number 82, February, 2004, A Survey on Private Information Retrieval
by William Gasarch       [PDF]   [Postscript]
Number 81, October, 2003, Is P Versus NP Formally Independent?
by Scott Aaronson        [PDF]   [Postscript]
Number 80, June, 2003, A Short History of Computational Complexity
by Lance Fortnow and Steve Homer        [PDF]   [Postscript]
Number 79, February, 2003, A Physics-Free Introduction to the Quantum Computation Model
by Stephen Fenner
Number 78, October, 2002, Understanding the Mulmuley-Sohoni Approach to P vs. NP
by Kenneth Regan        [PDF]   [Postscript]
Number 77, June, 2002, Recent Developments in Explicit Constructions of Extractors
by Ronen Shaltiel        [PDF]   [Postscript]
Number 76, February, 2002, Derandomization: A Brief Overview
by Valentine Kabanets
Number 75, October, 2001, The Art of Uninformed Decisions: A Primer to Property Testing
by Eldar Fischer.
Number 74, June, 2001, The Division Breakthroughs
by Eric Allender.
Number 73, February, 2001, Time-Space Lower Bounds for Satisfiability
by Dieter van Melkebeek.
Number 72, October, 2000, A Survey of Constant Time Parallel Sorting
by William Gasarch, Evan Golub and Clyde Kruskal.
Number 71, June, 2000, Diagonalization
by Lance Fortnow.
Number 70, February, 2000, Low-discrepancy Sets for High-dimensional Rectangles: A Survey
by Aravind Srinivasan .
Number 69, October, 1999, Computational Tractability: The View From Mars
by Rodney G. Downey, Michael R. Fellows, and Ulrike Stege.
Number 68, June, 1999, Twelve Problems in Resource-Bounded Measure (Update)
by Jack Lutz and Elvira Mayordomo.
Number 67, February, 1999, Progress in Descriptive Complexity
by Neil Immerman.
Number 66, October, 1998, News from the Isomorphism Front
by Eric Allender.
Number 65, June, 1998, Propositional Proof Complexity: Past, Present, and Future
by Paul Beame, and Toniann Pitassi.
Number 64, February, 1998, Recent advances towards proving P=BPP
by Andrea E. F. Clementi, José D. P. Rolim, and Luca Trevisan.
Number 63, October, 1997, An introduction to query order
by Edith Hemaspaandra, Lane A. Hemaspaandra, and Harald Hempel.
Number 62, June, 1997, Some pointed questions concerning asymptotic lower bounds
by Eric Allender (with a report by Jack Lutz).
Number 58, February, 1996, On Regularity-Preserving Functions
by Dexter Kozen.
Number 57, October, 1995, A Foundation of Computable Analysis
by Klaus Weihrauch.
Number 55, February, 1995, On the Weight of Computations
by Juris Hartmanis.
Number 54, October, 1994, A Machine Model for NP-approximation Problems and the Revenge of the Boolean Hierarchy
by Richard Chang.
Number 53, June, 1994, About the Nature of Computer Science
by Juris Hartmanis.
Number 52, February, 1994, The Role of Relativization in complexity theory
by Lance Fortnow.
Number 51, October, 1993, Information-Based Complexity
by J. Traub and H. Wozniakowski.
Number 49, February, 1993, A Broader Research Agenda for Theory
by Juris Hartmanis.
Number 47, June, 1992, Relativization: a Revisionistic Retrospective
by Juris Hartmanis, Richard Chang, S. Chari, D. Ranjan, and P. Rohatgi, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 537-547.
Number 46, February, 1992, Is #P Closed under Subtraction?
by Lane Hemachandra and Mitsunori Ogiwara in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 523-536.
Number 45, October, 1991, Complexity Classes for Partial Functions
by Alan Selman, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 504-522.
Number 42, October, 1990, On Unique Satisfiability and Random Reductions
by Richard Chang and P. Rohatgi, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 494-503.
Number 41, June, 1990, On IP = PSPACE and Theorems with Narrow Proofs
by Juris Hartmanis, Richard Chang, D. Ranjan, and P. Rohatgi, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 484-493.
Number 40, February, 1990, Counting hierarchies: polynomial time and constant depth circuits
by Eric Allender and Klaus W. Wagner), in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 469--483.
Number 39, October, 1989, A View of Structural Complexity Theory
by Ron Book and Osamu Watanabe, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 451--468.
Number 38, June, 1989, Gödel, von Neumann and the P=?NP Problem
by Juris Hartmanis, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 445--450.
Number 37, February, 1989, On the Importance of Being Pi_2-Hard
by Juris Hartmanis, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 435--444.
Number 36, October, 1988, Self-Reducibility: The Effects of Structure on Complexity
by Deborah Joseph and Paul Young.
Number 35, June, 1988, Some Observations about Relativizations of Space Bounded Computations
by Juris Hartmanis, Richard Chang, J. Kadin and S. Mitchell, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 423--433.
Number 33, October, 1987, Collapsing Hierarchies
by Juris Hartmanis, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 412--434.
Number 32, June, 1987, Sparse Complete Sets for NP and the Optimal Collapse of the Polynomial Hierarchy
by Juris Hartmanis, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 403--411.
Number 31, February, 1987, A Retrospective on Structural Complexity
by Juris Hartmanis, in Current Trends in Theoretical Computer Science, G. Rozenberg and A. Salomaa, ed., World Scientific Series in Computer Science, Vol. 40, World Scientific Press, 1993, pp. 397--402.