Volume 8 (2012)
 Volume 8, Article 1 (pages 1-51) Time-Space Efficient Simulations of Quantum Computations
 Volume 8, Article 2 (pages 53-54) [Motwani Special Issue] Special Issue in Honor of Rajeev Motwani (1962-2009): Guest Editors' Foreword by Samir Khuller and Sudipto Guha
 Volume 8, Article 3 (pages 55-68) [Motwani Special Issue] Rajeev Motwani (1962-2009)
 Volume 8, Article 4 (pages 69-94) [Motwani Special Issue] Regularity Lemmas and Combinatorial Algorithms by Nikhil Bansal and Ryan Williams
 Volume 8, Article 5 (pages 95-119) [Motwani Special Issue] Revenue Submodularity
 Volume 8, Article 6 (pages 121-164) [RESEARCH SURVEY] The Multiplicative Weights Update Method: a Meta-Algorithm and Applications by Sanjeev Arora, Elad Hazan, and Satyen Kale
 Volume 8, Article 7 (pages 165-195) [Motwani Special Issue] Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor
 Volume 8, Article 8 (pages 197-208) The Communication Complexity of Gap Hamming Distance ■
 Volume 8, Article 9 (pages 209-229) [Motwani Special Issue] Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule by Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, and Kirk Pruhs
 Volume 8, Article 10 (pages 231-238) [NOTE] Monotone Circuits: One-Way Functions versus Pseudorandom Generators by Oded Goldreich and Rani Izsak
 Volume 8, Article 11 (pages 239-267) Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set
 Volume 8, Article 12 (pages 269-289) SDP Gaps from Pairwise Independence
 Volume 8, Article 13 (pages 291-319) Span-Program-Based Quantum Algorithm for Evaluating Formulas by Ben Reichardt and Robert Špalek
 Volume 8, Article 14 (pages 321-350) [Motwani Special Issue] Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
 Volume 8, Article 15 (pages 351-368) [Motwani Special Issue] One Tree Suffices: A Simultaneous $O(1)$-Approximation for Single-Sink Buy-at-Bulk by Ashish Goel and Ian Post
 Volume 8, Article 16 (pages 369-374) [NOTE] Quantum Private Information Retrieval with Sublinear Communication Complexity
 Volume 8, Article 17 (pages 375-400) On the Power of a Unique Quantum Witness
 Volume 8, Article 18 (pages 401-413) [Motwani Special Issue] An $O(k^3\log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design by Julia Chuzhoy and Sanjeev Khanna
 Volume 8, Article 19 (pages 415-428) Distance Transforms of Sampled Functions
 Volume 8, Article 20 (pages 429-460) [Motwani Special Issue] Budget-Constrained Auctions with Heterogeneous Items
 Volume 8, Article 21 (pages 461-486) Two-Source Extractors Secure Against Quantum Adversaries by Roy Kasher and Julia Kempe
 Volume 8, Article 22 (pages 487-512) Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction
 Volume 8, Article 23 (pages 513-531) Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors by Ishay Haviv and Oded Regev
 Volume 8, Article 24 (pages 533-565) Solving Packing Integer Programs via Randomized Rounding with Alterations
 Volume 8, Article 25 (pages 567-595) [Motwani Special Issue] Online Graph Edge-Coloring in the Random-Order Arrival Model
 Volume 8, Article 26 (pages 597-622) A Constant-Factor Approximation Algorithm for Co-clustering
 Volume 8, Article 27 (pages 623-645) Near-Optimal and Explicit Bell Inequality Violations