|
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 3, Article 11 (pages 211-219)
The Randomized Communication Complexity of Set Disjointness by Johan Håstad and Avi Wigderson |
|
Volume 3, Article 10 (pages 197-209)
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem by Chandra Chekuri and Martin Pál |
■
|
|
Volume 3, Article 9 (pages 179-195)
Approximation Algorithms and Online Mechanisms for Item Pricing by Maria-Florina Balcan and Avrim Blum |
|
Volume 2, Article 9 (pages 173-183)
Tolerant Versus Intolerant Testing for Boolean Properties by Eldar Fischer and Lance Fortnow |
|
Volume 2, Article 7 (pages 137-146)
An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow by Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd |
|
Volume 2, Article 3 (pages 53-64)
An Improved Approximation Ratio for the Covering Steiner Problem by Anupam Gupta and Aravind Srinivasan |
|
Volume 1, Article 6 (pages 105-117)
Combining Online Algorithms for Acceptance and Rejection by Yossi Azar, Avrim Blum, David P. Bunde, and Yishay Mansour |
|
Volume 1, Article 3 (pages 37-46)
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range by Andris Ambainis |
|
Volume 1, Article 2 (pages 29-36)
Quantum Lower Bound for the Collision Problem with Small Range by Samuel Kutin |