**A Direct Sum Theorem for Corruption and the Multiparty NOF Communication
Complexity of Disjointness** by Paul Beame, Toniann Pitassi, Nathan Segerlind,
Avi Wigderson

**A Geometric Approach to Information-Theoretic Private Information Retrieval**
by David Woodruff and Sergey Yekhanin

**Average-Case Computations -- Comparing AvgP, HP, and Nearly-P** by Arfst
Nickelsen and Birgit Schelm

**Better Time-Space Lower Bounds for SAT and Related Problems** by Ryan
Williams

**Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy** by V.
Arvind and Piyush P Kurur and T.C. Vijayaraghavan

**Computationally-Private Randomizing Polynomials and Their Applications** by
Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

**Hardness of Max 3SAT with No Mixed Clauses** by Venkatesan Guruswami,
Subhash Khot

**If NP languages are hard on the worst-case then it is easy to find their hard
instances** by Dan Gutfreund and Ronen Shaltiel and Amnon Ta-Shma

**Monotone Circuits for Weighted Threshold Functions** by Amos Beimel and
Enav Weinreb

**More on noncommutative polynomial identity testing** by Andrej Bogdanov and
Hoeteck Wee

**NP with Small Advice **by Lance Fortnow and Adam Klivans

**New Results on the Complexity of the Middle Bit of Multiplication** by Ingo
Wegener and Philipp Woelfel

**On Constructing Parallel Pseudorandom Generators from One-Way Functions**
by Emanuele Viola

**On the Complexity of Hardness Amplification** by Chi-Jen Lu, Shi-Chun Tsai,
Hsin-Lung Wu

**On the Fourier Spectrum of Symmetric Boolean Functions with Applications to
Learning Symmetric Juntas** by Richard Lipton, Evangelos Markakis, Aranyak
Mehta, Nisheeth Vishnoi

**On the Hardness of Approximating Multicut and Sparsest-Cut** by Shuchi
Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani and D.Sivakumar

**On the Ring Isomorphism & Automorphism Problems** by Neeraj Kayal, Nitin
Saxena

**On the Sensitivity of Cyclically-Invariant Boolean Functions** by Sourav
Chakraborty

**On the complexity of succinct zero-sum games** by L. Fortnow and R.
Impagliazzo and V. Kabanets and C. Umans

**On the hardness of distinguishing mixed-state quantum computations** by
Bill Rosgen and John Watrous

**Prior entanglement, message compression and privacy in quantum communication**
by Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen

**Pseudorandom Bits for Constant Depth Circuits with One Arbitrary Symmetric
Gate** by Emanuele Viola

**Pseudorandomness for Approximate Counting and Sampling** by Ronen Shaltiel
and Chris Umans

**Short PCPs verifiiable in polylogarithmic time** by Eli Ben-Sasson, Oded
Goldriech, Prahladh Harsha, Madhu Sudan and Salil Vadhan

**The Complexity of the Inertia and some Closure Properties of GapL** by
Thanh Minh Hoang and Thomas Thierauf

**The quantum adversary method and formula size lower bounds** by S.
Laplante, T. Lee, and M. Szegedy

**Tolerant Versus Intolerant Testing for Boolean Properties** by Eldar
Fischer and Lance Fortnow

**Topology inside NC1 **by Eric Allender, Samir Datta, Sambuddha Roy

**Toward a Model for Backtracking and Dynamic Programming** by M. Alekhnovich,
A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, T. Pitassi

**Upper Bounds for Quantum Interactive Proofs with Competing Provers** by Gus
Gutoski