Theory of Computing, Volume 3

Volume 3, Number 1, 2007

• Amos Fiat, Jared Saia:
  Censorship Resistant Peer-to-Peer Networks. 1-23
  Electronic Edition (link) BibTeX
• Uriel Feige, Eran Ofek:
  Easily refutable subformulas of large random 3CNF formulas. 25-43
  Electronic Edition (link) BibTeX
• Ishay Haviv, Oded Regev, Amnon Ta-Shma:
  On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy. 45-60
  Electronic Edition (link) BibTeX
• Dominik Janzing, Pawel Wocjan:
  A Simple PromiseBQP-complete Matrix Problem. 61-79
  Electronic Edition (link) BibTeX
• Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart:
  An Exponential Separation between Regular and General Resolution. 81-102
  Electronic Edition (link) BibTeX
• David Zuckerman:
  Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. 103-128
  Electronic Edition (link) BibTeX
• Scott Aaronson, Greg Kuperberg:
  Quantum Versus Classical Proofs and Advice. 129-157
  Electronic Edition (link) BibTeX
• Jirí Matousek, Petr Skovron:
  Removing Degeneracy May Require a Large Dimension Increase. 159-177
  Electronic Edition (link) BibTeX
• Maria-Florina Balcan, Avrim Blum:
  Approximation Algorithms and Online Mechanisms for Item Pricing. 179-195
  Electronic Edition (link) BibTeX
• Chandra Chekuri, Martin Pál:
  An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem. 197-209
  Electronic Edition (link) BibTeX
• Johan Håstad, Avi Wigderson:
  The Randomized Communication Complexity of Set Disjointness. 211-219
  Electronic Edition (link) BibTeX
• Alexander A. Razborov, Sergey Yekhanin:
  An Omega(n^1/3) Lower Bound for Bilinear Group Based Private Information Retrieval. 221-238
  Electronic Edition (link) BibTeX