Volume 11 (2015)
Vol 11, Article 1 (pp 1-34)
The Complexity of Deciding Statistical Properties of Samplable Distributions
by Thomas Watson
The Complexity of Deciding Statistical Properties of Samplable Distributions
by Thomas Watson
Vol 11, Article 2 (pp 35-57)
The Complexity of Parity Graph Homomorphism: An Initial Investigation
by John Faben and Mark Jerrum
The Complexity of Parity Graph Homomorphism: An Initial Investigation
by John Faben and Mark Jerrum
Vol 11, Article 3 (pp 59-103)
Quantum Interactive Proofs and the Complexity of Separability Testing
by Gus Gutoski, Patrick Hayden, Kevin Milner, and Mark M. Wilde
Quantum Interactive Proofs and the Complexity of Separability Testing
by Gus Gutoski, Patrick Hayden, Kevin Milner, and Mark M. Wilde
Vol 11, Article 4 (pp 105-147)
Maximizing the Spread of Influence through a Social Network
by David Kempe, Jon Kleinberg, and Éva Tardos
Maximizing the Spread of Influence through a Social Network
by David Kempe, Jon Kleinberg, and Éva Tardos
Vol 11, Article 6 (pp 183-219)
How Hard Is It to Approximate the Jones Polynomial?
by Greg Kuperberg
How Hard Is It to Approximate the Jones Polynomial?
by Greg Kuperberg
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
The Projection Games Conjecture and the NP-Hardness of ln $n$-Approximating Set-Cover
by Dana Moshkovitz
Vol 11, Article 8 (pp 237-239)
[APRX-RND13 Spec Issue]
Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword
by Sofya Raskhodnikova and Ola Svensson
Special Issue: APPROX-RANDOM 2013: Guest Editors' Foreword
by Sofya Raskhodnikova and Ola Svensson
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
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
by Shayan Oveis Gharan and Luca Trevisan
Vol 11, Article 10 (pp 257-283)
[APRX-RND13 Spec Issue]
On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
by Per Austrin, Rajsekar Manokaran, and Cenny Wenner
On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
by Per Austrin, Rajsekar Manokaran, and Cenny Wenner
Vol 11, Article 11 (pp 285-298)
New Lower Bounds for the Border Rank of Matrix Multiplication
by Joseph M. Landsberg and Giorgio Ottaviani
New Lower Bounds for the Border Rank of Matrix Multiplication
by Joseph M. Landsberg and Giorgio Ottaviani
Vol 11, Article 12 (pp 299-338)
[APRX-RND13 Spec Issue]
Absolutely Sound Testing of Lifted Codes
by Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan
Absolutely Sound Testing of Lifted Codes
by Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan
Vol 11, Article 13 (pp 339-355)
Computing the Partition Function for Cliques in a Graph
by Alexander Barvinok
Computing the Partition Function for Cliques in a Graph
by Alexander Barvinok
Vol 11, Article 14 (pp 357-393)
Non-Commutative Arithmetic Circuits with Division
by Pavel Hrubeš and Avi Wigderson
Non-Commutative Arithmetic Circuits with Division
by Pavel Hrubeš and Avi Wigderson
Vol 11, Article 15 (pp 395-401)
[NOTE]
Groups with Identical $k$-Profiles
by George Glauberman and Łukasz Grabowski
Groups with Identical $k$-Profiles
by George Glauberman and Łukasz Grabowski
Vol 11, Article 16 (pp 403-412)
[NOTE]
Quantum Algorithm for Monotonicity Testing on the Hypercube
by Aleksandrs Belovs and Eric Blais
Quantum Algorithm for Monotonicity Testing on the Hypercube
by Aleksandrs Belovs and Eric Blais
Vol 11, Article 17 (pp 413-443)
[APRX-RND13 Spec Issue]
Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration
by Emmanuel Abbe and Andrea Montanari
Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration
by Emmanuel Abbe and Andrea Montanari
Vol 11, Article 18 (pp 445-469)
[Boolean Spec Issue]
On some extensions of the FKN theorem
by Jacek Jendrej, Krzysztof Oleszkiewicz, and Jakub O. Wojtaszczyk
On some extensions of the FKN theorem
by Jacek Jendrej, Krzysztof Oleszkiewicz, and Jakub O. Wojtaszczyk
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
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
by Joshua Brody and Kasper Green Larsen
Vol 11, Article 20 (pp 491-603)
The Bose-Hubbard Model is QMA-complete
by Andrew M. Childs, David Gosset, and Zak Webb
The Bose-Hubbard Model is QMA-complete
by Andrew M. Childs, David Gosset, and Zak Webb