Articles under category:
Short Communications
Short Communications
|
Vol 18, Article 18 (pp 1-19)
Algorithms for Intersection Graphs for $t$-Intervals and $t$-Pseudodisks by Chandra Chekuri and Tanmay Inamdar |
|
Vol 18, Article 10 (pp 1-12)
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines by Emanuele Viola |
|
Vol 18, Article 9 (pp 1-18)
[APRX-RND19 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 1-18)
[CCC18 Spec Issue]
The Cayley Semigroup Membership Problem by Lukas Fleischer |
|
Vol 16, Article 9 (pp 1-12)
On the Complexity of Computing a Random Boolean Function Over the Reals by Pavel Hrubeš |
|
Vol 16, Article 6 (pp 1-20)
Sharp Bounds for Population Recovery by Anindya De, Ryan O'Donnell, and Rocco A. Servedio |
|
Vol 15, Article 18 (pp 1-9)
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds by Emanuele Viola |
|
Vol 15, Article 11 (pp 1-13)
Fourier Sparsity and Dimension by Swagato Sanyal |
|
Vol 14, Article 13 (pp 1-17)
On the Hardness of Learning With Errors with Binary Secrets by Daniele Micciancio |
|
Vol 13, Article 18 (pp 1-15)
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds by Joshua A. Grochow |
|
Vol 13, Article 14 (pp 1-17)
[APRX-RND15 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 1-19)
On the Hardness of Approximating Balanced Homogenous 3-Lin by Johan Håstad and Rajsekar Manokaran |
|
Vol 13, Article 7 (pp 1-18)
A Communication Game Related to the Sensitivity Conjecture by Justin Gilmer, Michal Koucký, and Michael Saks |
|
Vol 12, Article 14 (pp 1-14)
[APRX-RND15 Spec Issue]
Minimizing Maximum Flow-Time on Related Machines by Nikhil Bansal and Bouke Cloostermans |
|
Vol 12, Article 11 (pp 1-17)
Anti-concentration for Polynomials of Independent Random Variables by Raghu Meka, Oanh Nguyen, and Van Vu |
|
Vol 12, Article 5 (pp 1-14)
A Tradeoff Between Length and Width in Resolution by Neil Thapen |
|
Vol 11, Article 19 (pp 471-489)
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures by Joshua Brody and Kasper Green Larsen |
|
Vol 11, Article 13 (pp 339-355)
Computing the Partition Function for Cliques in a Graph by Alexander Barvinok |
|
Vol 11, Article 11 (pp 285-298)
New Lower Bounds for the Border Rank of Matrix Multiplication by Joseph M. Landsberg and Giorgio Ottaviani |
|
Vol 11, Article 9 (pp 241-256)
[APRX-RND13 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 221-235)
[APRX-RND12 Spec Issue]
The Projection Games Conjecture and the NP-Hardness of ln $n$-Approximating Set-Cover by Dana Moshkovitz |
|
Vol 10, Article 19 (pp 515-533)
Query Complexity Lower Bounds for Reconstruction of Codes by Sourav Chakraborty, Eldar Fischer, and Arie Matsliah |
|
Vol 10, Article 17 (pp 453-464)
An Optimal Lower Bound for Monotonicity Testing over Hypergrids by Deeparnab Chakrabarty and C. Seshadhri |
|
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 |