Articles under category:
Short Communications
Vol 9, Article 20 (pp 653-663)
Approximating the AND-OR Tree
by Alexander A. Sherstov
Vol 9, Article 10 (pp 403-411)
On the Real $\tau$-Conjecture and the Distribution of Complex Roots
by Pavel Hrubeš
Vol 9, Article 7 (pp 283-293)
Pseudorandomness for Width-2 Branching Programs
by Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff
Vol 8, Article 19 (pp 415-428)
Distance Transforms of Sampled Functions
by Pedro F. Felzenszwalb and Daniel P. Huttenlocher
Vol 8, Article 8 (pp 197-208)
The Communication Complexity of Gap Hamming Distance
by Alexander A. Sherstov
Vol 7, Article 9 (pp 131-145)
Inverse Conjecture for the Gowers Norm is False
by Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky
Vol 7, Article 8 (pp 119-129)
Arithmetic Complexity in Ring Extensions
by Pavel Hrubeš and Amir Yehudayoff
Vol 5, Article 12 (pp 239-255)
Tensor Products of Weakly Smooth Codes are Robust
by Eli Ben-Sasson and Michael Viderman
Vol 5, Article 6 (pp 125-134)
Hard Metrics from Cayley Graphs of Abelian Groups
by Ilan Newman and Yuri Rabinovich
Vol 5, Article 3 (pp 69-82)
Unconditional Pseudorandom Generators for Low Degree Polynomials
by Shachar Lovett
Vol 4, Article 6 (pp 129-135)
The One-Way Communication Complexity of Hamming Distance
by T. S. Jayram, Ravi Kumar, and D. Sivakumar
Vol 3, Article 11 (pp 211-219)
The Randomized Communication Complexity of Set Disjointness
by Johan Håstad and Avi Wigderson
Vol 3, Article 10 (pp 197-209)
An   O(log n)   Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
by Chandra Chekuri and Martin Pál
Vol 3, Article 9 (pp 179-195)
Approximation Algorithms and Online Mechanisms for Item Pricing
by Maria-Florina Balcan and Avrim Blum
Vol 2, Article 9 (pp 173-183)
Tolerant Versus Intolerant Testing for Boolean Properties
by Eldar Fischer and Lance Fortnow
Vol 2, Article 7 (pp 137-146)
An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow
by Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd
Vol 2, Article 3 (pp 53-64)
An Improved Approximation Ratio for the Covering Steiner Problem
by Anupam Gupta and Aravind Srinivasan
Vol 1, Article 6 (pp 105-117)
Combining Online Algorithms for Acceptance and Rejection
by Yossi Azar, Avrim Blum, David P. Bunde, and Yishay Mansour
Vol 1, Article 3 (pp 37-46)
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
by Andris Ambainis
Vol 1, Article 2 (pp 29-36)
Quantum Lower Bound for the Collision Problem with Small Range
by Samuel Kutin