Title: Quantum Certificate Complexity
Author(s):
Scott Aaronson
Title: Derandomization and Distinguishing Complexity.
Author(s): Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy.
Title: Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness
Author(s): Amit Chakrabarti and Subhash Khot and Xiaodong Sun
Title: Uniform Hardness vs. Randomness Tradeoffs for Arthur-Merlin Games
Author(s): Dan Gutreund and Ronen Shaltiel and Amnon Ta-Shma
Title: Universal Languages and the Power of Diagonalization
Author(s): Alan Nash and Russell Impagliazzo and Jeff Remmel
Title: Extracting the Mutual Information for a Triple of Binary Strings
Author(s): Andrei E. Romashchenko
Title: A Combinatorial Characterization of Resolution Width
Author(s): Albert Atserias and Victor Dalmau
Title: Quantum decision trees and semidefinite programming
Author(s): Howard Barnum and Michael Saks and Mario Szegedy
Title: Memoization and DPLL: Formula Caching Proof Systems
Author(s): Paul Beame and Russell Impagliazzo and Toniann Pitassi and Nathan Segerlind
Title: Three-Query PCPs with Perfect Completeness over non-Boolean Domains
Author(s): Lars Engebretsen and Jonas Holmerin
Title: Are Cook and Karp Ever the Same?
Author(s): Richard Beigel and Lance Fortnow
Title: Disjoint NP-Pairs
Author(s): Christian Glaßer and Alan L. Selman and Samik Sengupta and Liyu Zhang
Title: Bounded Nondeterminism and Alternation in Parameterized Complexity Theory
Author(s): Yijia Chen and Joerg Flum and Martin Grohe
Title: A Strong Inapproximability Result for a Generalization of Minimum Bisection.
Author(s): Jonas Holmerin and Subhash Khot
Title: The complexity of Unique k-SAT: An isolation lemma for k-CNFs
Author(s): Chris Calabro and Russell Impagliazzo and Valentine Kabanets and Ramamohan Paturi
Title: Rectangle Size Bounds and Threshold Covers in Communication Complexity
Author(s): Hartmut Klauck
Title: The complexity of stochastic sequences
Author(s): Wolfgang Merkle
Title: A zero-one law for RP
Author(s): Russell Impagliazzo and Philippe Moser
Title: Improved Inapproximability of Lattice and Coding Problems with Preprocessing
Author(s): Oded Regev
Title: Vertex Cover Might be Hard to Approximate to within 2-e
Author(s): Subhash Khot and Oded Regev
Title: Extremal properties of polynomial threshold functions
Author(s): Ryan O'Donnell and Rocco Servedio
Title: Proving SAT does not have Small Circuits with an Application to the Two Queries Problem
Author(s): Lance Fortnow and A. Pavan and Samik Sengupta
Title: Lower bounds for predecessor searching in the cell probe model
Author(s): Pranab Sen
Title: Holographic Proofs and Derandomization
Author(s): Rahul Santhanam and Dieter van Melkebeek
Title: Minimization of Decision Trees is Hard to Approximate
Author(s): Detlef Sieling
Title: Optimal Separation of EROW and CROW PRAMs
Author(s): Navin Goyal and Michael Saks and S. Venkatesh
Title: List decoding with side information
Author(s): Venkatesan Guruswami
Title: Hardness vs. Randomness within Uniform AC0
Author(s): Emanuele Viola
Title: On Statistical Query Sampling and NMR Quantum Computing
Author(s): Avrim Blum and Ke Yang