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 |