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
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