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, R. 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 |