Volume 12 (2016)
Vol 12, Article 1 (pp 1-61) [APRX-RND13 Spec Issue]
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
by Amos Beimel, Kobbi Nissim, and Uri Stemmer
Vol 12, Article 2 (pp 1-34)
Lattice Sparsification and the Approximate Closest Vector Problem
by Daniel Dadush and Gábor Kun
Vol 12, Article 3 (pp 1-42)
Interactive Proofs for $\mathsf{BQP}$ via Self-Tested Graph States
by Matthew McKague
Vol 12, Article 4 (pp 1-50)
Majority is Stablest: Discrete and SoS
by Anindya De, Elchanan Mossel, and Joe Neeman
Vol 12, Article 5 (pp 1-14)
A Tradeoff Between Length and Width in Resolution
by Neil Thapen
Vol 12, Article 6 (pp 1-11) [NOTE]
Simple Proof of Hardness of Feedback Vertex Set
by Venkatesan Guruswami and Euiwoong Lee
Vol 12, Article 7 (pp 1-27)
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
by Swastik Kopparty, Mrinal Kumar, and Michael Saks
Vol 12, Article 8 (pp 1-3) [APRX-RND14 Spec Issue]
Special Issue: APPROX-RANDOM 2014: Guest Editors' Foreword
by Deeparnab Chakrabarty and David Galvin
Vol 12, Article 9 (pp 1-23) [APRX-RND14 Spec Issue]
Communication Complexity of Set-Disjointness for All Probabilities
by Mika Göös and Thomas Watson
Vol 12, Article 10 (pp 1-35)
Robust Lower Bounds for Communication and Stream Computation
by Amit Chakrabarti, Graham Cormode, and Andrew McGregor
Vol 12, Article 11 (pp 1-17)
Anti-concentration for Polynomials of Independent Random Variables
by Raghu Meka, Oanh Nguyen, and Van Vu
Vol 12, Article 12 (pp 1-38)
Lower Bounds for Non-Commutative Skew Circuits
by Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan
Vol 12, Article 13 (pp 1-3) [APRX-RND15 Spec Issue]
Special Issue: APPROX-RANDOM 2015: Guest Editors' Foreword
by Nicole Megow and Mary Wootters
Vol 12, Article 14 (pp 1-14) [APRX-RND15 Spec Issue]
Minimizing Maximum Flow-Time on Related Machines
by Nikhil Bansal and Bouke Cloostermans
Vol 12, Article 15 (pp 1-29) [APRX-RND14 Spec Issue]
Lowest-Degree $k$-Spanner: Approximation and Hardness
by Eden Chlamtáč and Michael Dinitz
Vol 12, Article 16 (pp 1-34)
Dual Polynomials for Collision and Element Distinctness
by Mark Bun and Justin Thaler
Vol 12, Article 17 (pp 1-25) [APRX-RND14 Spec Issue]
Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion
by Anand Louis and Yury Makarychev
Vol 12, Article 18 (pp 1-35)
Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman Bomb Tester
by Cedric Yen-Yu Lin and Han-Hsuan Lin
Vol 12, Article 19 (pp 1-33)
Locally Checkable Proofs in Distributed Computing
by Mika Göös and Jukka Suomela
Vol 12, Article 20 (pp 1-25)
Dichotomies in Equilibrium Computation and Membership of PLC Markets in FIXP
by Jugal Garg, Ruta Mehta, and Vijay V. Vazirani
List of Editors