Volume 18, 2011
: Impossibility of Succinct Quantum Proofs for Collision-Freeness.
: Testing Linear Properties: Some general themes.
: Pseudorandom Generators with Long Stretch and Low locality from Random Local One-Way Functions.
: NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth.
, Or Meir
: Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly.
: New strong direct product results in communication complexity.
: Monotone Rank and Separations in Computational Complexity.
, Bin Fu
: A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing.
, Andrew Mills
: Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length.
: Graphs of Bounded Treewidth can be Canonized in AC1.
, Marek Kosta
: Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable.
: On the query complexity for Showing Dense Model.
: Efficiently Coding for Interactive Communication.
: A Linear-Optical Proof that the Permanent is #P-Hard.
, Shachar Lovett
: Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions.
: A concentration inequality for the overlap of a vector on a large set, With application to the communication complexity of the Gap-Hamming-Distance problem.
, Xi Wu
: Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization.
: Secure Computation with Information Leaking to an Adversary.
: A tighter lower bound on the circuit size of the hardest Boolean functions.
: A Combination of Testability and Decodability by Tensor Products.
: How much commutativity is needed to prove polynomial identities?
: Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions.
: Complexity Dichotomies of Counting Problems.
: Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem.
: Determinism Versus Nondeterminism with Arithmetic Tests and Computation.
: Combinatorial PCPs with efficient verifiers.
: On Computational Power of Partially Blind Automata.
: Why Philosophers Should Care About Computational Complexity.
: The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover.
: Reducing 3XOR to listing triangles, an exposition.
: Computational Bottlenecks for Evolvability.
: Advice Lower Bounds for the Dense Model Theorem.
: Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators.
: Dispersers for affine sources with sub-polynomial entropy.
, Shafi Goldwasser
: Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications.
: Complexity Lower Bounds through Balanced Graph Properties.
: From Irreducible Representations to Locally Decodable Codes.
: Design Extractors, Non-Malleable Condensers and Privacy Amplification.
: A lower bound on the size of resolution proofs of the Ramsey theorem.
: Non-Malleable Extractors for Entropy Rate <1/2.
Nikolay K. Vereshchagin
: Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances".
: Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation.