EATCS
Bulletin Computational Complexity Column
The Computational Complexity Column of the EATCS Bulletin was started
by
Juris Hartmanis in 1987.
The previous editors of the column:
Juris Hartmanis (during 1987-1997)
Eric Allender (during 1997-2000)
Lance Fortnow (during 2000-2004)
Jacobo Toran (during 2004-2011)
Since June 2011 I am serving as the column editor. Please email me if
you have any suggestions/comments for future column topics.
The Articles
- Number 118, February, 2016, Catalytic Computation
- by
Michal Koucký
[PDF]
[PS]
- Number 117, October, 2015, Lowness Results: the next
generation
- by
Johannes Köbler and
Jacobo Torán
[PDF]
[PS]
- Number 116, June, 2015, Combinatorial Game
Complexity: an introduction with Poset Games
- by
Stephen A. Fenner and
John Rogers
[PDF]
[PS]
- Number 115, February, 2015, Robust Oracle Machines
Revisited
- by
V. Arvind
[PDF]
[PS]
- Number 114, October, 2014, Recent Progress on Arithmetic
Circuit Lower Bounds
- by
Ramprasad Saptharishi
[PDF]
[PS]
- Number 113, June, 2014, Recent Developments in Kernelization:
a Survey
- by
Stefan Kratsch
[PDF]
[PS]
- Number 112, February, 2014, Recent Advances on the Log-Rank Conjecture in Communication Complexity
- by
Shachar Lovett
[PDF]
[PS]
- Number 111, October, 2013, The Alon-Roichman Theorem
- by
V. Arvind
[PDF]
[PS]
- Number 109, February, 2013, Space Complexity: What makes Planar Graphs Special?
- by
Samir Datta and
Raghav Kulkarni
[PDF]
[PS]
- Number 108, October, 2012, Complexity of Model Checking For Logics over Kripke Models
- by
Arner Meier and
Julian-Steffen Müller
and Martin
Mundhenk and
Heribert Vollmer
[PDF]
[PS]
- Number 107, June, 2012, Around and beyond the Isomorphism Problem for Interval Graphs
- by
Johannes Köbler and
Sebastian Kuhnert and Oleg Verbisky
[PDF]
[PS]
- Number 106, February, 2012, Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds
- by
Rahul Santhanam
[PDF]
[PS]
- Number 105, October, 2011, Lower Bounds based on the Exponential-Time Hypothesis
- by Daniel
Lokshtanov and
Daniel Marx and
Saket Saurabh
[PDF]
[PS]
- Number 104, June, 2011, Noncommutative Arithmetic Circuits
meet Finite Automata
- by
V. Arvind
[PDF]
[PS]
- 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.