Volume 10 (2014)
Vol 10, Article 1 (pp 1-26) [Boolean Spec Issue]
Bounding the Sensitivity of Polynomial Threshold Functions
by Prahladh Harsha, Adam Klivans, and Raghu Meka
Vol 10, Article 2 (pp 27-53)
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions
by Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan
Vol 10, Article 3 (pp 55-75) [Boolean Spec Issue]
Dimension-Free $L_2$ Maximal Inequality for Spherical Means in the Hypercube
by Aram W. Harrow, Alexandra Kolla, and Leonard J. Schulman
Vol 10, Article 4 (pp 77-105)
Grothendieck Inequalities for Semidefinite Programs with Rank Constraint
by Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin
Vol 10, Article 5 (pp 107-131)
Competing-Provers Protocols for Circuit Evaluation
by Gillat Kol and Ran Raz
Vol 10, Article 6 (pp 133-166)
The Need for Structure in Quantum Speedups
by Scott Aaronson and Andris Ambainis
Vol 10, Article 7 (pp 167-197) [RESEARCH SURVEY]
Matchgates Revisited
by Jin-Yi Cai and Aaron Gorenstein
Vol 10, Article 8 (pp 199-215)
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
by Eric Allender and Klaus-Jörn Lange
Vol 10, Article 9 (pp 217-236)
Improved Inapproximability for TSP
by Michael Lampis
Vol 10, Article 10 (pp 237-256)
Lower Bounds for the Average and Smoothed Number of Pareto-Optima
by Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Röglin
Vol 10, Article 11 (pp 257-295)
Efficient Rounding for the Noncommutative Grothendieck Inequality
by Assaf Naor, Oded Regev, and Thomas Vidick
Vol 10, Article 12 (pp 297-339)
Width-Parametrized SAT: Time--Space Tradeoffs
by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang
Vol 10, Article 13 (pp 341-358) [APRX-RND12 Spec Issue]
Approximation Algorithm for Non-Boolean Max-$k$-CSP
by Konstantin Makarychev and Yury Makarychev
Vol 10, Article 14 (pp 359-388)
Approximation Resistance on Satisfiable Instances for Sparse Predicates
by Sangxia Huang
Vol 10, Article 15 (pp 389-419) [Boolean Spec Issue]
Tight Bounds for Monotone Switching Networks via Fourier Analysis
by Siu Man Chan and Aaron Potechin
Vol 10, Article 16 (pp 421-451)
How Many Bits Can a Flock of Birds Compute?
by Bernard Chazelle
Vol 10, Article 17 (pp 453-464)
An Optimal Lower Bound for Monotonicity Testing over Hypergrids
by Deeparnab Chakrabarty and C. Seshadhri
Vol 10, Article 18 (pp 465-514)
On Reconstruction and Testing of Read-Once Formulas
by Amir Shpilka and Ilya Volkovich
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 20 (pp 535-570)
Learning $k$-Modal Distributions via Testing
by Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio
List of Editors