Articles under category:
Short Communications
Short Communications
Vol 19, Article 11 (pp 114)
A Strong XOR Lemma for Randomized Query Complexity by Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu 
Vol 18, Article 18 (pp 119)
Algorithms for Intersection Graphs for $t$Intervals and $t$Pseudodisks by Chandra Chekuri and Tanmay Inamdar 
Vol 18, Article 10 (pp 112)
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines by Emanuele Viola 
Vol 18, Article 9 (pp 118)
[APRXRND19 Spec Issue]
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions by Zongchen Chen and Santosh S. Vempala 
Vol 18, Article 8 (pp 118)
[CCC18 Spec Issue]
The Cayley Semigroup Membership Problem by Lukas Fleischer 
Vol 16, Article 9 (pp 112)
On the Complexity of Computing a Random Boolean Function Over the Reals by Pavel Hrubeš 
Vol 16, Article 6 (pp 120)
Sharp Bounds for Population Recovery by Anindya De, Ryan O'Donnell, and Rocco A. Servedio 
Vol 15, Article 18 (pp 19)
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds by Emanuele Viola 
Vol 15, Article 11 (pp 113)
Fourier Sparsity and Dimension by Swagato Sanyal 
Vol 14, Article 13 (pp 117)
On the Hardness of Learning With Errors with Binary Secrets by Daniele Micciancio 
Vol 13, Article 18 (pp 115)
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds by Joshua A. Grochow 
Vol 13, Article 14 (pp 117)
[APRXRND15 Spec Issue]
A Randomized Online Quantile Summary in $O((1/\varepsilon) \log(1/\varepsilon))$ Words by David Felber and Rafail Ostrovsky 
Vol 13, Article 10 (pp 119)
On the Hardness of Approximating Balanced Homogenous 3Lin by Johan Håstad and Rajsekar Manokaran 
Vol 13, Article 7 (pp 118)
A Communication Game Related to the Sensitivity Conjecture by Justin Gilmer, Michal Koucký, and Michael Saks 
Vol 12, Article 14 (pp 114)
[APRXRND15 Spec Issue]
Minimizing Maximum FlowTime on Related Machines by Nikhil Bansal and Bouke Cloostermans 
Vol 12, Article 11 (pp 117)
Anticoncentration for Polynomials of Independent Random Variables by Raghu Meka, Oanh Nguyen, and Van Vu 
Vol 12, Article 5 (pp 114)
A Tradeoff Between Length and Width in Resolution by Neil Thapen 
Vol 11, Article 19 (pp 471489)
Adapt or Die: Polynomial Lower Bounds for NonAdaptive Dynamic Data Structures by Joshua Brody and Kasper Green Larsen 
Vol 11, Article 13 (pp 339355)
Computing the Partition Function for Cliques in a Graph by Alexander Barvinok 
Vol 11, Article 11 (pp 285298)
New Lower Bounds for the Border Rank of Matrix Multiplication by Joseph M. Landsberg and Giorgio Ottaviani 
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 LowDegree 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 