|
Volume 4, Article 8 (pages 169-190) A Quantum Algorithm for the Hamiltonian NAND Tree by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann |
|
Volume 4, Article 7 (pages 137-168) Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols by Emanuele Viola and Avi Wigderson |
|
Volume 4, Article 6 (pages 129-135) The One-Way Communication Complexity of Hamming Distance by T. S. Jayram, Ravi Kumar, and D. Sivakumar |
|
Volume 4, Article 5 (pages 111-128) Approximation Algorithms for Unique Games by Luca Trevisan |
|
Volume 4, Article 4 (pages 77-109) Near-Optimal Network Design with Selfish Agents by Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, and Tom Wexler |
|
Volume 4, Article 3 (pages 53-76) Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications by Avi Wigderson and David Xiao |
|
Volume 4, Article 2 (pages 21-51) Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem by Miklós Ajtai |
|
Volume 4, Article 1 (pages 1-20) Single Source Multiroute Flows and Cuts on Uniform Capacity Networks by Henning Bruhn, Jakub Černý, Alexander Hall, Petr Kolman, and Jiří Sgall |