of the
Computational Complexity Column
Editor,
Previous Editors:
, June
2000 - February 2004
, June
1997 - February 2000
, February 1987 - February 1996
edits a sister column for .
Please contact the
if you have any
comments on the column or suggestions for future column topics.
Complexity Links
-
-
-
-
Articles
- Number 103, February, 2011, On the Notion of Bit Complexity
- by
[PDF]
[PS]
- Number 102, October, 2010, Complexity of Non-Monotonic Logics
- by
and
[PDF]
[PS]
- Number 101, June, 2010, Researching the Complexity of Boolean
Functions with Computers
- by
[PDF]
[PS]
- Number 100, February, 2010, Multilinear Polynomial Modulo Composites
- by
[PDF]
[PS]
- Number 99, October, 2009, Progress in Polynomial Identity Testing
- by
[PDF]
[PS]
- Number 98, June, 2009, Integer Multiplication and the Complexity of
Binary Decision Diagrams
- by
[PDF]
[PS]
- Number 97, February, 2009, The Complexity of Planar Graph Isomorphism
- by and
[PDF]
[PS]
- Number 95, June, 2008, Communication Lower Bounds Using Dual Polynomials
- by
[PDF]
[PS]
- Number 94, February, 2008, Kolmogorov Complexity and Games
- by
[PDF]
[PS]
- Number 93, October, 2007, Quantum Computing and the Hunt for
Hidden Symmetry
- by
and
[PDF]
- Number 91, February, 2007, Polynomial Size Log Depth Circuits:
Between NC1 and AC1
- by
[PDF]
[Postscript]
- Number 90, October, 2006, Iterative Decoding of Low-Density Parity Check Codes
- by
[PDF]
[Postscript]
- Number 89, June, 2006, Learning Boolean Functions under the uniform distribution via
the Fourier Transform
- by and
[PDF]
[Postscript]
- Number 88, February, 2006, Bridges between Algebraic Automata Theory
and Complexity Theory
- by and
[PDF]
[Postscript]
- Number 87, October, 2005, Lower Bounds on Quantum Query Complexity
- by and
[PDF]
[Postscript]
- Number 86, June, 2005, Isomorphism Testing: Perspective and Open
Problems
- by and
[PDF]
[Postscript]
- Number 85, February, 2005, A Post's Program For Complexity Theory
- by and
[PDF]
- Number 84, October , 2004, Parametrized Complexity and Subexponential
Time
- by and
[PDF]
[Postscript]
- Number 83, June, 2004, Space and Width in Propositional Resolution
- by
[PDF]
[Postscript]
- Number 82, February, 2004, A Survey on Private Information
Retrieval
- by
[PDF]
[Postscript]
- Number 81, October, 2003, Is P Versus NP Formally
Independent?
-
by
[PDF]
[Postscript]
- Number 80, June, 2003, A Short History of Computational
Complexity
- by
and
[PDF]
[Postscript]
- Number 79, February, 2003,
A Physics-Free Introduction to the Quantum Computation
Model
- by
- Number 78, October, 2002,
Understanding the Mulmuley-Sohoni Approach to P vs. NP
- by
[PDF]
[Postscript]
- Number 77, June, 2002, Recent Developments in Explicit
Constructions of Extractors
- by
[PDF]
[Postscript]
- Number 76, February, 2002,
Derandomization: A Brief Overview
- by
- Number 75, October, 2001, The Art of
Uninformed Decisions: A Primer to Property Testing
- by
.
- Number 74, June, 2001,
The Division Breakthroughs
- by
,
Time-Space Lower Bounds for Satisfiability
- by
.
- Number 72, October, 2000, A Survey of
Constant Time Parallel Sorting
- by ,
and
.
- Number 71, June, 2000, Diagonalization
- by
.
- Number 70, February, 2000,
Low-discrepancy
Sets for High-dimensional Rectangles: A Survey
- by ,
Computational
Tractability: The View From Mars
- by .
- Number 68, June, 1999,
Twelve
Problems in Resource-Bounded Measure ()
- by .
- Number 67, February, 1999,
Progress
in Descriptive Complexity
- by ,
News
from the Isomorphism Front
- by ,
Propositional
Proof Complexity: Past, Present, and Future
- by
.
- Number 64, February, 1998,
Recent
advances towards proving P=BPP
- by
, and
,
An
introduction to query order
- by Edith Hemaspaandra,
.
- Number 62, June, 1997, Some
pointed questions concerning asymptotic lower bounds
- by ).
- Number 58, February, 1996,
On
Regularity-Preserving Functions
- by
- by ,
A Machine
Model for NP-approximation Problems and the Revenge of the
Boolean Hierarchy
- by .
- Number 52, February, 1994,
The
Role of Relativization in complexity theory
- by
.
- Number 51, October, 1993,
Information-Based Complexity
- by .
- Number 49, February, 1993,
A Broader Research Agenda for Theory
- by
- by ,
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
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 ,
On Unique
Satisfiability and Random Reductions
- by ,
On IP = PSPACE
and Theorems with Narrow Proofs
- by , 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 ),
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
- by
- by
- by ,
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
- by
- 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.