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.