Theory of Computing, Volume 4

Volume 4, Number 1, 2008

• Henning Bruhn, Jakub Cerný, Alexander Hall, Petr Kolman, Jiri Sgall:
  Single Source Multiroute Flows and Cuts on Uniform Capacity Networks. 1-20
  
• Miklós Ajtai:
  Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem. 21-51
  
• Avi Wigderson, David Xiao:
  Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. 53-76
  
• Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, Tom Wexler:
  Near-Optimal Network Design with Selfish Agents. 77-109
  
• Luca Trevisan:
  Approximation Algorithms for Unique Games. 111-128
  
• T. S. Jayram, Ravi Kumar, D. Sivakumar:
  The One-Way Communication Complexity of Hamming Distance. 129-135
  
• Emanuele Viola, Avi Wigderson:
  Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. 137-168
  
• Edward Farhi, Jeffrey Goldstone, Sam Gutmann:
  A Quantum Algorithm for the Hamiltonian NAND Tree. 169-190
  
• Viswanath Nagarajan:
  On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem. 191-193