Articles under category:
Short Communications
Short Communications
Vol 11, Article 9 (pp 241256)
[APRXRND13 Spec Issue]
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs by Shayan Oveis Gharan and Luca Trevisan 
Vol 11, Article 7 (pp 221235)
[APRXRND12 Spec Issue]
The Projection Games Conjecture and the NPHardness of ln $n$Approximating SetCover by Dana Moshkovitz 
Vol 10, Article 19 (pp 515533)
Query Complexity Lower Bounds for Reconstruction of Codes by Sourav Chakraborty, Eldar Fischer, and Arie Matsliah 
Vol 10, Article 17 (pp 453464)
An Optimal Lower Bound for Monotonicity Testing over Hypergrids by Deeparnab Chakrabarty and C. Seshadhri 
Vol 9, Article 20 (pp 653663)
Approximating the ANDOR Tree by Alexander A. Sherstov 
Vol 9, Article 10 (pp 403411)
On the Real $\tau$Conjecture and the Distribution of Complex Roots by Pavel Hrubeš 
Vol 9, Article 7 (pp 283293)
Pseudorandomness for Width2 Branching Programs by Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff 
Vol 8, Article 19 (pp 415428)
Distance Transforms of Sampled Functions by Pedro F. Felzenszwalb and Daniel P. Huttenlocher 
Vol 8, Article 8 (pp 197208)
The Communication Complexity of Gap Hamming Distance by Alexander A. Sherstov 
■

Vol 7, Article 9 (pp 131145)
Inverse Conjecture for the Gowers Norm is False by Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky 
Vol 7, Article 8 (pp 119129)
Arithmetic Complexity in Ring Extensions by Pavel Hrubeš and Amir Yehudayoff 
Vol 5, Article 12 (pp 239255)
Tensor Products of Weakly Smooth Codes are Robust by Eli BenSasson and Michael Viderman 
Vol 5, Article 6 (pp 125134)
Hard Metrics from Cayley Graphs of Abelian Groups by Ilan Newman and Yuri Rabinovich 
Vol 5, Article 3 (pp 6982)
Unconditional Pseudorandom Generators for Low Degree Polynomials by Shachar Lovett 
Vol 4, Article 6 (pp 129135)
The OneWay Communication Complexity of Hamming Distance by T. S. Jayram, Ravi Kumar, and D. Sivakumar 
Vol 3, Article 11 (pp 211219)
The Randomized Communication Complexity of Set Disjointness by Johan Håstad and Avi Wigderson 
Vol 3, Article 10 (pp 197209)
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 179195)
Approximation Algorithms and Online Mechanisms for Item Pricing by MariaFlorina Balcan and Avrim Blum 
Vol 2, Article 9 (pp 173183)
Tolerant Versus Intolerant Testing for Boolean Properties by Eldar Fischer and Lance Fortnow 
Vol 2, Article 7 (pp 137146)
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 5364)
An Improved Approximation Ratio for the Covering Steiner Problem by Anupam Gupta and Aravind Srinivasan 
Vol 1, Article 6 (pp 105117)
Combining Online Algorithms for Acceptance and Rejection by Yossi Azar, Avrim Blum, David P. Bunde, and Yishay Mansour 
Vol 1, Article 3 (pp 3746)
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range by Andris Ambainis 
Vol 1, Article 2 (pp 2936)
Quantum Lower Bound for the Collision Problem with Small Range by Samuel Kutin 