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

- 1.
- 2013 Abstracts

Volume 2012

Published articles