|
Volume 4, Article 9 (pages 191-193)
[COMMENT]
On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem by Viswanath Nagarajan |
|
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 |