CCC 2011: Accepted papers

Non-Uniform ACC Circuit Lower Bounds
Ryan Williams (IBM Almaden)

Improved Direct Product Theorems for Randomized Query Complexity
Andrew Drucker (MIT)

Improved pseudorandomness for regular branching programs
Anindya De (University of California, Berkeley)

Symmetry-assisted adversaries for quantum state generation
Andris Ambainis (University of Latvia) Loick Magnin (UL-Brussels, University Paris 11, NEC Laboratories America), Martin Roetteler (NEC Laboratories America), and Jérémie Roland (NEC Laboratories America)

Explicit Dimension Reduction and Its Applications
Zohar S. Karnin (Technion), Yuval Rabani (Hebrew University), and Amir Shpilka (Technion and MSR)

On the Minimal Fourier Degree of Symmetric Boolean Functions
Amir Shpilka (Technion and MSR) and Avishay Tal (Technion)

A New Approach to Affine Extractors and Dispersers
Xin Li (University of Texas at Austin)

Property Testing Lower Bounds Via Communication Complexity
Eric Blais (Carnegie Mellon University), Joshua Brody (ITCS, IIIS, Tsinghua University), and Kevin Matulef (ITCS, IIIS, Tsinghua University)

Towards lower bounds on locally testable codes via density arguments
Eli Ben-Sasson (Technion) and Michael Viderman (Technion)

On Arthur Merlin Games in Communication Complexity
Hartmut Klauck (CQT and Nanyang Technological University).

Linear-algebraic list decoding of folded Reed-Solomon codes
Venkatesan Guruswami (Carnegie Mellon University)

Non-negatively Weighted #CSPs: An Effective Complexity Dichotomy, Jin-Yi Cai
(University of Wisconsin – Madison and Beijing University) Xi Chen (Columbia University), and Pinyan Lu (Microsoft Research Asia)

Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs
Yuichi Yoshida (Kyoto University and Preferred Infrastructure)

Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae
Matthew Anderson (University of Wisconsin – Madison), Dieter van Melkebeek (University of Wisconsin – Madison), and Ilya Volkovich (Technion)

Tensor Rank: Some Lower and Upper Bounds
Boris Alexeev (Princeton University), Michael Forbes (MIT), and Jacob Tsimerman (Princeton University)

Symmetric LDPC codes are not necessarily locally testable
Eli Ben-Sasson (Technion), Ghid Maatouk (EPFL), Amir Shpilka (Technion and MSR) and Madhu Sudan (MSR)

Bounded-depth circuits cannot sample good codes
Shachar Lovett (Institute of Advanced Study) and Emanuele Viola (Northeastern University)

Noisy Interpolation of Sparse Polynomials, and Applications
Shubhangi Saraf (MIT) and Sergey Yekhanin (Microsoft Research)

Linear Systems Over Finite Abelian Groups
Arkadev Chattopadhyay (University of Toronto) and Shachar Lovett (Institute for Advanced Study)

Relativized Separations of Worst-Case and Average-Case Complexities for NP
Russell Impagliazzo (IAS and UCSD)

Symmetry of Information and bounds on nonuniform randomness extraction via Kolmogorov extractors
Marius Zimand (Towson University)

Paris-Harrington tautologies
Lorenzo Carlucci (Sapienza - Universita di Roma), Nicola Galesi (Sapienza - Universita di Roma) and Massimo Lauria (Sapienza - Universita di Roma)

Near-Optimal and Explicit Bell Inequality Violations
Harry Buhrman (CWI and University of Amsterdam), Oded Regev (Tel Aviv University and ENS, Paris), Giannicola Scarpa (CWI), and Ronald de Wolf (CWI and University of Amsterdam)

Approximation algorithms for QMA-complete problems
Sevag Gharibian (University of Waterloo) and Julia Kempe (Tel Aviv University and CNRS, University of Paris 7)

Making Branching Programs Oblivious Requires Superlogarithmic Overhead
Paul Beame (University of Washington) and Widad Machmouchi (University of Washington)

k-independent Gaussians Fools Polynomial Threshold Functions
Daniel M. Kane (Harvard University)

Pseudorandom Generators for Combinatorial Checkerboards
Thomas Watson (University of California, Berkeley)

Improved Constructions of Three Source Extractors
Xin Li (University of Texas at Austin)

On the Sum of Square Roots of Polynomials and Related Problems
Neeraj Kayal (Microsoft Research India) and Chandan Saha (Max Planck Institute for Informatics)

Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups
Ryan O'Donnell (CMU), Yi Wu (IBM Almaden Research), and Yuan Zhou (CMU)