Volume 5 (2009)
Vol 5, Article 1 (pp 1-42)
The Power of Unentanglement
by Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor
Vol 5, Article 2 (pp 43-67)
Deterministic History-Independent Strategies for Storing Information on Write-Once Memories
by Tal Moran, Moni Naor, and Gil Segev
Vol 5, Article 3 (pp 69-82)
Unconditional Pseudorandom Generators for Low Degree Polynomials
by Shachar Lovett
Vol 5, Article 4 (pp 83-117)
SDP Gaps and UGC-hardness for Max-Cut-Gain
by Subhash Khot and Ryan O'Donnell
Vol 5, Article 5 (pp 119-123) [NOTE]
Discrete-Query Quantum Algorithm for NAND Trees
by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo
Vol 5, Article 6 (pp 125-134)
Hard Metrics from Cayley Graphs of Abelian Groups
by Ilan Newman and Yuri Rabinovich
Vol 5, Article 7 (pp 135-140) [NOTE]
A Simple Proof of Toda's Theorem
by Lance Fortnow
Vol 5, Article 8 (pp 141-172)
Parallel Repetition: Simplification and the No-Signaling Case
by Thomas Holenstein
Vol 5, Article 9 (pp 173-189)
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time
by Virginia Vassilevska, Ryan Williams, and Raphael Yuster
Vol 5, Article 10 (pp 191-216)
Distribution-Free Testing Lower Bound for Basic Boolean Functions
by Dana Glasner and Rocco A. Servedio
Vol 5, Article 11 (pp 217-238)
Semidefinite Programs for Completely Bounded Norms
by John Watrous
Vol 5, Article 12 (pp 239-255)
Tensor Products of Weakly Smooth Codes are Robust
by Eli Ben-Sasson and Michael Viderman
Vol 5, Article 13 (pp 257-282)
Optimal Cryptographic Hardness of Learning Monotone Functions
by Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, and Hoeteck Wee
List of Editors