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