Volume 8 (2012)
Vol 8, Article 1 (pp 1-51)
Time-Space Efficient Simulations of Quantum Computations by Dieter van Melkebeek and Thomas Watson |
Vol 8, Article 2 (pp 53-54)
[Motwani Special Issue]
Special Issue in Honor of Rajeev Motwani (1962-2009): Guest Editors' Foreword by Samir Khuller and Sudipto Guha |
Vol 8, Article 3 (pp 55-68)
[Motwani Special Issue]
Rajeev Motwani (1962-2009) by Prabhakar Raghavan |
Vol 8, Article 4 (pp 69-94)
[Motwani Special Issue]
Regularity Lemmas and Combinatorial Algorithms by Nikhil Bansal and R. Ryan Williams |
Vol 8, Article 5 (pp 95-119)
[Motwani Special Issue]
Revenue Submodularity by Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan |
Vol 8, Article 6 (pp 121-164)
[RESEARCH SURVEY]
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications by Sanjeev Arora, Elad Hazan, and Satyen Kale |
Vol 8, Article 7 (pp 165-195)
[Motwani Special Issue]
Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor by Chandra Chekuri, Sungjin Im, and Benjamin Moseley |
Vol 8, Article 8 (pp 197-208)
The Communication Complexity of Gap Hamming Distance by Alexander A. Sherstov |
■
|
Vol 8, Article 9 (pp 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 |
Vol 8, Article 10 (pp 231-238)
[NOTE]
Monotone Circuits: One-Way Functions versus Pseudorandom Generators by Oded Goldreich and Rani Izsak |
Vol 8, Article 11 (pp 239-267)
Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set by Venkatesan Guruswami and Yuan Zhou |
Vol 8, Article 12 (pp 269-289)
SDP Gaps from Pairwise Independence by Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani |
Vol 8, Article 13 (pp 291-319)
Span-Program-Based Quantum Algorithm for Evaluating Formulas by Ben Reichardt and Robert Špalek |
Vol 8, Article 14 (pp 321-350)
[Motwani Special Issue]
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality by Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani |
Vol 8, Article 15 (pp 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 |
Vol 8, Article 16 (pp 369-374)
[NOTE]
Quantum Private Information Retrieval with Sublinear Communication Complexity by François Le Gall |
Vol 8, Article 17 (pp 375-400)
On the Power of a Unique Quantum Witness by Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang |
Vol 8, Article 18 (pp 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 |
Vol 8, Article 19 (pp 415-428)
Distance Transforms of Sampled Functions by Pedro F. Felzenszwalb and Daniel P. Huttenlocher |
Vol 8, Article 20 (pp 429-460)
[Motwani Special Issue]
Budget-Constrained Auctions with Heterogeneous Items by Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala |
Vol 8, Article 21 (pp 461-486)
Two-Source Extractors Secure Against Quantum Adversaries by Roy Kasher and Julia Kempe |
Vol 8, Article 22 (pp 487-512)
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction by Daniele Micciancio |
Vol 8, Article 23 (pp 513-531)
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors by Ishay Haviv and Oded Regev |
Vol 8, Article 24 (pp 533-565)
Solving Packing Integer Programs via Randomized Rounding with Alterations by Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan |
Vol 8, Article 25 (pp 567-595)
[Motwani Special Issue]
Online Graph Edge-Coloring in the Random-Order Arrival Model by Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani |
Vol 8, Article 26 (pp 597-622)
A Constant-Factor Approximation Algorithm for Co-clustering by Aris Anagnostopoulos, Anirban Dasgupta, and Ravi Kumar |
Vol 8, Article 27 (pp 623-645)
Near-Optimal and Explicit Bell Inequality Violations by Harry Buhrman, Oded Regev, Giannicola Scarpa, and Ronald de Wolf |
List of Editors |