default search action
Theory of Computing, Volume 8
Volume 8, Number 1, 2012
- Dieter van Melkebeek, Thomas Watson:
Time-Space Efficient Simulations of Quantum Computations. 1-51 - Samir Khuller, Sudipto Guha:
Special Issue in Honor of Rajeev Motwani (1962-2009): Guest Editors' Foreword. 53-54 - Prabhakar Raghavan:
Rajeev Motwani (1962-2009). 55-68 - Nikhil Bansal, Ryan Williams:
Regularity Lemmas and Combinatorial Algorithms. 69-94 - Shaddin Dughmi, Tim Roughgarden, Mukund Sundararajan:
Revenue Submodularity. 95-119 - Sanjeev Arora, Elad Hazan, Satyen Kale:
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. 121-164 - Chandra Chekuri, Sungjin Im, Benjamin Moseley:
Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor. 165-195 - Alexander A. Sherstov:
The Communication Complexity of Gap Hamming Distance. 197-208 - Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, Kirk Pruhs:
Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule. 209-229 - Oded Goldreich, Rani Izsak:
Monotone Circuits: One-Way Functions versus Pseudorandom Generators. 231-238 - Venkatesan Guruswami, Yuan Zhou:
Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set. 239-267 - Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, Madhur Tulsiani:
SDP Gaps from Pairwise Independence. 269-289 - Ben Reichardt, Robert Spalek:
Span-Program-Based Quantum Algorithm for Evaluating Formulas. 291-319 - Sariel Har-Peled
, Piotr Indyk, Rajeev Motwani:
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality. 321-350 - Ashish Goel, Ian Post:
One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk. 351-368 - François Le Gall:
Quantum Private Information Retrieval with Sublinear Communication Complexity. 369-374 - Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath
On the Power of a Unique Quantum Witness. 375-400 - Julia Chuzhoy, Sanjeev Khanna:
An O(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. 401-413 - Pedro F. Felzenszwalb, Daniel P. Huttenlocher:
Distance Transforms of Sampled Functions. 415-428 - Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala:
Budget-Constrained Auctions with Heterogeneous Items. 429-460 - Roy Kasher, Julia Kempe:
Two-Source Extractors Secure Against Quantum Adversaries. 461-486 - Daniele Micciancio
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction. 487-512 - Ishay Haviv, Oded Regev:
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors. 513-531 - Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, Aravind Srinivasan
Solving Packing Integer Programs via Randomized Rounding with Alterations. 533-565 - Bahman Bahmani, Aranyak Mehta, Rajeev Motwani:
Online Graph Edge-Coloring in the Random-Order Arrival Model. 567-595 - Aris Anagnostopoulos
A Constant-Factor Approximation Algorithm for Co-clustering. 597-622 - Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf:
Near-Optimal and Explicit Bell Inequality Violations. 623-645
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-18 20:34 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: