Volume 9 (2013)
Vol 9, Article 1 (pp 1-29)
The Power of Nondeterminism in Self-Assembly by Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki |
Vol 9, Article 2 (pp 31-116)
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems by Daniel Gottesman and Sandy Irani |
Vol 9, Article 3 (pp 117-142)
Inapproximability of NP-Complete Variants of Nash Equilibrium by Per Austrin, Mark Braverman, and Eden Chlamtáč |
Vol 9, Article 4 (pp 143-252)
The Computational Complexity of Linear Optics by Scott Aaronson and Alex Arkhipov |
Vol 9, Article 5 (pp 253-272)
Constructing Small-Bias Sets from Algebraic-Geometric Codes by Avraham Ben-Aroya and Amnon Ta-Shma |
Vol 9, Article 6 (pp 273-282)
[NOTE]
The Complexity of the Fermionant and Immanants of Constant Width by Stephan Mertens and Cristopher Moore |
Vol 9, Article 7 (pp 283-293)
Pseudorandomness for Width-2 Branching Programs by Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff |
Vol 9, Article 8 (pp 295-347)
Testing Properties of Collections of Distributions by Reut Levi, Dana Ron, and Ronitt Rubinfeld |
Vol 9, Article 9 (pp 349-401)
Quantum Money from Hidden Subspaces by Scott Aaronson and Paul Christiano |
Vol 9, Article 10 (pp 403-411)
On the Real $\tau$-Conjecture and the Distribution of Complex Roots by Pavel Hrubeš |
Vol 9, Article 11 (pp 413-435)
Improved Inapproximability Results for Maximum $k$-Colorable Subgraph by Venkatesan Guruswami and Ali Kemal Sinop |
Vol 9, Article 12 (pp 437-439)
[APRX-RND12 Spec Issue]
Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword by Alexandr Andoni and Atri Rudra |
Vol 9, Article 13 (pp 441-470)
[APRX-RND12 Spec Issue]
Optimal Hitting Sets for Combinatorial Shapes by Aditya Bhaskara, Devendra Desai, and Srikanth Srinivasan |
Vol 9, Article 14 (pp 471-557)
Towards an Optimal Separation of Space and Length in Resolution by Jakob Nordström and Johan Håstad |
Vol 9, Article 15 (pp 559-577)
[APRX-RND12 Spec Issue]
Almost $k$-Wise vs. $k$-Wise Independent Permutations, and Uniformity for General Group Actions by Noga Alon and Shachar Lovett |
Vol 9, Article 16 (pp 579-585)
[Boolean Spec Issue]
Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword by Elchanan Mossel and Ryan O'Donnell |
Vol 9, Article 17 (pp 587-592)
[NOTE]
[Boolean Spec Issue]
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta by Daniel Kane |
Vol 9, Article 18 (pp 593-615)
[Boolean Spec Issue]
Making Polynomials Robust to Noise by Alexander A. Sherstov |
Vol 9, Article 19 (pp 617-651)
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems by Uriel Feige, Elchanan Mossel, and Dan Vilenchik |
Vol 9, Article 20 (pp 653-663)
Approximating the AND-OR Tree by Alexander A. Sherstov |
Vol 9, Article 21 (pp 665-683)
[APRX-RND12 Spec Issue]
Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic by Eli Ben-Sasson and Ariel Gabizon |
Vol 9, Article 22 (pp 685-702)
Hamming Approximation of NP Witnesses by Daniel Sheldon and Neal E. Young |
Vol 9, Article 24 (pp 759-781)
[APRX-RND12 Spec Issue]
Hardness of Vertex Deletion and Project Scheduling by Ola Svensson |
Vol 9, Article 25 (pp 783-807)
[APRX-RND12 Spec Issue]
A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes by Noga Ron-Zewi and Madhu Sudan |
Vol 9, Article 26 (pp 809-843)
On Beating the Hybrid Argument by Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola |
Vol 9, Article 27 (pp 845-862)
[Boolean Spec Issue]
Satisfying Degree-$d$ Equations over $GF[2]^n$ by Johan Håstad |
Vol 9, Article 28 (pp 863-887)
[Boolean Spec Issue]
A Two-Prover One-Round Game with Strong Soundness by Subhash Khot and Muli Safra |
Vol 9, Article 29 (pp 889-896)
[NOTE]
[Boolean Spec Issue]
Hypercontractivity Via the Entropy Method by Eric Blais and Li-Yang Tan |
Vol 9, Article 30 (pp 897-945)
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream by Kai-Min Chung, Michael Mitzenmacher, and Salil Vadhan |
List of Editors |