Volume 37, Number 1, 2007
: Lower Bounds for Quantum Communication Complexity.
, Daqing Wan
: On the List and Bounded Distance Decodability of Reed-Solomon Codes.
: A Polynomial Time Algorithm for Computing an Arrow-Debreu Market Equilibrium for Linear Utilities.
Volume 37, Number 2, 2007
, Yuval Rabani
: Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems.
: One-Way Communication Complexity and the Ne[c-caron]iporuk Lower Bound on Formula Size.
, Jochen Könemann
: Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.
Volume 37, Number 3, 2007
Volume 37, Number 4, 2007
, Wei Wang
: Geometric Separators and Their Applications to Protein Folding in the HP-Model.
, Martin Grohe
: An Isomorphism Between Subexponential and Parameterized Complexity Theory.
Volume 37, Number 5, 2008
, David Hay
: Randomization Does Not Reduce the Average Delay in Parallel Packet Switches.
Andrew V. Goldberg
: A Practical Shortest Path Algorithm with Linear Expected Time.
: The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case.
Volume 37, Number 6, 2008
, Asaf Shapira
: A Characterization of the (Natural) Graph Properties Testable with One-Sided Error.
Philip N. Klein
: A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights.