A 3-Query Non-Adaptive PCP with Perfect Completeness
Subhash Khot, Rishi Saket
A Generic Time Hierarchy for Semantic Models with One Bit of Advice
Dieter van Melkebeek, Konstantin Pervyshev
A Duality Between Clause Width and Clause Density for SAT
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi
An Isomorphism between Subexponential and Parameterized Complexity Theory
Yijia Chen, Martin Grohe
Circuit lower bounds via Ehrenfeucht-Fraisse games
Michal Koucky, Clemens Lautemann, Sebastian Poloczek, Denis Therien
Constructing Ramsey Graphs from Boolean Function Representations
Parikshit Gopalan
Construction of Low-Degree and Error-Correcting \epsilon-Biased Sets
Amir Shpilka
Derandomization of Probabilistic Auxiliary Pushdown Automata Classes
H. Venkateswaran
Every Linear Threshold Function has a Low-Weight Approximator
Rocco A. Servedio
Exposure-Resilient Extractors
Marius Zimand
FO[<]-Uniformity
C. Behle, K.-J. Lange
Grid Graph Reachability Problems
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta,
Sambuddha Roy
Hardness of the Covering Radius Problem on Lattices
Ishay Haviv, Oded Regev
How to get more mileage from randomness extractors
Ronen Shaltiel
Learning Monotone Decision Trees in Polynomial Time
Ryan O'Donnell, Rocco Servedio
Making Hard Problems Harder
Joshua Buresh-Oppenheim, Rahul Santhanam
Minimizing DNF formulas and AC^0_d circuits given a truth table
Eric Allender, Lisa Hellerstein, Paul McCabe, Toni Pitassi, Michael Saks
New lower bounds for Vertex Cover in the Lovasz-Schrijver hierarchy
Iannis Tourlakis
Non-uniform Hardness for NP against Black-Box Samplers
Albert Atserias
On Arthur-Merlin Games and the Possibility of Basing Cryptography on NP-Hardness
Rafael Pass
On Modular Counting with Polynomials
Kristoffer Arnsfelt Hansen
On the Complexity of Numerical Analysis
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro
Miltersen
Optimal Hardness Results for Maximizing Agreements with Monomials
Vitaly Feldman
Oracles Are Subtle But Not Malicious
Scott Aaronson
Polynomial Identity Testing for Depth 3 Circuits
Neeraj Kayal, Nitin Saxena
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
Scott Aaronson
Random Measurement Bases, Quantum State Distinction and Applications to the
Hidden Subgroup Problem
Pranab Sen
Strengths and Weaknesses of Quantum Fingerprinting
Dmitry Gavinsky, Julia Kempe, Ronald de Wolf