Articles under category:
Short Communications: Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science

Articles under category:
Short Communications

Vol 20, Article 4 (pp 1-13) [Boolean Spec Issue]
Influential Coalitions for Boolean Functions I: Constructions
by Jean Bourgain, Jeff Kahn, and Gil Kalai

Vol 19, Article 11 (pp 1-14)
A Strong XOR Lemma for Randomized Query Complexity
by Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu

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