Volume 13 (2017)
Vol 13, Article 1 (pp 1-3)
[CCC16 Spec Issue]
Special Issue: CCC 2016: Guest Editor's Foreword by Prahladh Harsha |
Vol 13, Article 2 (pp 1-21)
[CCC16 Spec Issue]
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs by Rohit Gurjar, Arpita Korwar, and Nitin Saxena |
Vol 13, Article 3 (pp 1-24)
[APRX-RND15 Spec Issue]
Towards a Characterization of Approximation Resistance for Symmetric CSPs by Venkatesan Guruswami and Euiwoong Lee |
Vol 13, Article 4 (pp 1-22)
On the (Non) NP-Hardness of Computing Circuit Complexity by Cody D. Murray and R. Ryan Williams |
Vol 13, Article 5 (pp 1-47)
[APRX-RND13 Spec Issue]
A Pseudo-Approximation for the Genus of Hamiltonian Graphs by Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos |
Vol 13, Article 6 (pp 1-33)
[CCC16 Spec Issue]
Arithmetic Circuits with Locally Low Algebraic Rank by Mrinal Kumar and Shubhangi Saraf |
Vol 13, Article 7 (pp 1-18)
A Communication Game Related to the Sensitivity Conjecture by Justin Gilmer, Michal Koucký, and Michael Saks |
Vol 13, Article 8 (pp 1-22)
[APRX-RND15 Spec Issue]
The Minimum Bisection in the Planted Bisection Model by Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch |
Vol 13, Article 9 (pp 1-34)
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials by Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan |
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 11 (pp 1-36)
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals by Zeev Dvir, Shubhangi Saraf, and Avi Wigderson |
Vol 13, Article 12 (pp 1-50)
[APRX-RND14 Spec Issue]
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs by Thomas Steinke, Salil Vadhan, and Andrew Wan |
Vol 13, Article 13 (pp 1-31)
Nash Equilibria in Perturbation-Stable Games by Maria-Florina Balcan and Mark Braverman |
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 15 (pp 1-24)
Tight Hardness of the Non-Commutative Grothendieck Problem by Jop Briët, Oded Regev, and Rishi Saket |
Vol 13, Article 16 (pp 1-23)
Some Limitations of the Sum of Small-Bias Distributions by Chin Ho Lee and Emanuele Viola |
Vol 13, Article 17 (pp 1-41)
A Constructive Lovász Local Lemma for Permutations by David G. Harris and Aravind Srinivasan |
Vol 13, Article 18 (pp 1-15)
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds by Joshua A. Grochow |
Vol 13, Article 19 (pp 1-51)
[APRX-RND15 Spec Issue]
Improved NP-Inapproximability for $2$-Variable Linear Equations by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright |
Vol 13, Article 20 (pp 1-25)
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems by F. Bruce Shepherd and Adrian R. Vetta |
Vol 13, Article 21 (pp 1-38)
[CCC16 Spec Issue]
Decoding Reed–Muller Codes over Product Sets by John Y. Kim and Swastik Kopparty |
List of Editors |