Published by the Department of Computer Science University of Chicago.

• 2013 Articles
  • 1. A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the Gap-Hamming-Distance problem by Thomas Vidick
  • 2. Few Product Gates but Many Zeroes by Bernd Borchert, Pierre McKenzie, and Klaus Reinhardt
  • 3. A Turing Machine Resisting Isolated Bursts Of Faults by Ilir Çapuni, and Peter Gács
  • 4. Quantum Adversary (Upper) Bound by Shelby Kimmel
  • 5. Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic by Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, and Iddo Tzameret
  • 6. The non-adaptive query complexity of testing k-parities by Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf
  • 7. Interactive proofs with competing teams of no-signaling provers by Gus Gutoski
  • 8. Simpler semidefinite programs for completely bounded norms by John Watrous
  • 9. Complexity of the homomorphism extension problem in the random case by Alexandr Kazda
  • 10. On the complexity of solving linear congruences and computing nullspaces modulo a constant by Niel de Beaudrap
  • 11. Coherent state exchange in multi-prover quantum interactive proof systems by Debbie Leung, Ben Toner, and John Watrous
  • 12. A Lower Bound for Fourier Transform Computation in a Linear Model Over 2x2 Unitary Gates Using Matrix Entropy by Nir Ailon
  • 13. Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs by Parinya Chalermsook, Shiva Kintali, Richard J. Lipton, and Danupon Nanongkai
  • 14. Testing Booleanity and the Uncertainty Principle by Tom Gur and Omer Tamuz
• 2013 Abstracts

Volume 2012

Published articles