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.