Articles under category:
Special Issue
Vol 10, Article 3 (pp 55-75) [Boolean Spec Issue]
Dimension-Free $L_2$ Maximal Inequality for Spherical Means in the Hypercube
by Aram W. Harrow, Alexandra Kolla, and Leonard J. Schulman
Vol 10, Article 1 (pp 1-26) [Boolean Spec Issue]
Bounding the Sensitivity of Polynomial Threshold Functions
by Prahladh Harsha, Adam Klivans, and Raghu Meka
Vol 9, Article 29 (pp 889-896) [NOTE] [Boolean Spec Issue]
Hypercontractivity Via the Entropy Method
by Eric Blais and Li-Yang Tan
Vol 9, Article 28 (pp 863-887) [Boolean Spec Issue]
A Two-Prover One-Round Game with Strong Soundness
by Subhash Khot and Muli Safra
Vol 9, Article 27 (pp 845-862) [Boolean Spec Issue]
Satisfying Degree-$d$ Equations over $GF[2]^n$
by Johan Håstad
Vol 9, Article 25 (pp 783-807) [APRX-RND12 Spec Issue]
A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes
by Noga Ron-Zewi and Madhu Sudan
Vol 9, Article 24 (pp 759-781) [APRX-RND12 Spec Issue]
Hardness of Vertex Deletion and Project Scheduling
by Ola Svensson
Vol 9, Article 23 (pp 703-757) [APRX-RND12 Spec Issue]
Circumventing $d$-to-$1$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
by Cenny Wenner
Vol 9, Article 21 (pp 665-683) [APRX-RND12 Spec Issue]
Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic
by Eli Ben-Sasson and Ariel Gabizon
Vol 9, Article 18 (pp 593-615) [Boolean Spec Issue]
Making Polynomials Robust to Noise
by Alexander A. Sherstov
Vol 9, Article 17 (pp 587-592) [NOTE] [Boolean Spec Issue]
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta
by Daniel Kane
Vol 9, Article 16 (pp 579-585) [Boolean Spec Issue]
Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword
by Elchanan Mossel and Ryan O'Donnell
Vol 9, Article 15 (pp 559-577) [APRX-RND12 Spec Issue]
Almost $k$-Wise vs. $k$-Wise Independent Permutations, and Uniformity for General Group Actions
by Noga Alon and Shachar Lovett
Vol 9, Article 13 (pp 441-470) [APRX-RND12 Spec Issue]
Optimal Hitting Sets for Combinatorial Shapes
by Aditya Bhaskara, Devendra Desai, and Srinkath Srinivasan
Vol 9, Article 12 (pp 437-439) [APRX-RND12 Spec Issue]
Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword
by Alexandr Andoni and Atri Rudra
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 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 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 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 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 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 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 5 (pp 95-119) [Motwani Special Issue]
Revenue Submodularity
by Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan
Vol 8, Article 4 (pp 69-94) [Motwani Special Issue]
Regularity Lemmas and Combinatorial Algorithms
by Nikhil Bansal and Ryan Williams
Vol 8, Article 3 (pp 55-68) [Motwani Special Issue]
Rajeev Motwani (1962-2009)
by Prabhakar Raghavan
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