CCC 2012 Accepted papers

(In order of submission)

• Is the Valiant-Vazirani Isolation Lemma Improvable?
  Holger Dell (U Wisconsin, Madison), Valentine Kabanets (Simon Fraser U.), Dieter van Melkebeek (U Wisconsin, Madison), Osamu Watanabe (Tokyo Institute of Technology).


• Testing List H-Homomorphisms
  Yuichi Yoshida (Kyoto University and Preferred Infrastructure, Inc.)


• A Dichotomy for Real Weighted Holant Problems
  Sangxia Huang (KTH Royal Institute of Technology), Pinyan Lu (Microsoft Research Asia)


• Combinatorial PCPs with Short Proofs
  Or Meir (Stanford University)


• Hitting Set Generators for Sparse Polynomials over any Finite Fields
  Chi-Jen Lu (Academia Sinica)


• A Strong Parallel Repetition Theorem for Projection Games on Expanders
  Ran Raz (Weizmann Institute), Ricky Rosen (Princeton University)


• List Decoding Barnes-Wall Lattices
  Elena Grigorescu and Chris Peikert (Georgia Institute of Technology)


• Algebras of minimal multiplicative complexity
  Markus Bläser (Saarland University), Bekhan Chokaev (Moscow State University)


• Parallel approximation of min-max problems with applications to classical and quantum zero-sum games
  Gus Gutoski (University of Waterloo), Xiaodi Wu (University of Michigan)


• A strong direct product theorem for quantum query complexity
  Troy Lee (Centre for Quantum Technologies), Jérémie Roland (Université Libre de Bruxelles)


• The Complexity of the Separable Hamiltonian Problem
  André Chailloux (UC Berkeley, California), Or Sattath (Hebrew University of Jerusalem)


• Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification
  Gil Cohen and Ran Raz (Weizmann Institute), Gil Segev (MSR Silicon Valley)


• On sunflowers and matrix multiplication
  Noga Alon (Tel Aviv University), Amir Shpilka (Technion), Christopher Umans (Caltech)


• Better condensers and new extractors from Parvaresh-Vardy codes
  Amnon Ta-Shma (Tel-Aviv University), Christopher Umans (Caltech)


• Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games
  Baris Aydinlioglu (University of Wisconsin-Madison), Dieter van Melkebeek (University of Wisconsin-Madison)


• Limits on Alternation-Trading Proofs for Time-Space Lower Bounds
  Samuel R. Buss (University of California, San Diego), Ryan Williams (Stanford University)


• Matrix Lie Algebra Isomorphism
  Joshua A. Grochow (The University of Chicago)


• On Problems as Hard as CNFSAT
  Marek Cygan (University of Lugano), Holger Dell (University of Wisconsin-Madison), Daniel Lokshtanov (University of California, San Diego), Daniel Marx (Hungarian Academy of Sciences), Jesper Nederlof (Utrecht University), Yoshio Okamoto, (Japan Advanced Institute of Science and Technology), Ramamohan Paturi (University of California, San Diego), Saket Saurabh (Institute of Mathematical Sciences, India), Magnus Wahlstrom (Max-Planck-Institut fur Informatik)


• Quantum Money with Classical Verification
  Dmitry Gavinsky (NEC Laboratories America, Inc.)


• A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis
  Kazuhisa Seto and Suguru Tamaki (Kyoto University)


• Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators
  Andrew Drucker (MIT)


• Share Conversion and Private Information Retrieval
  Amos Beimel (Ben-Gurion University), Yuval Ishai (Technion), Eyal Kushilevitz (Technion), Ilan Orlov (Ben-Gurion University)


• Space-efficient algorithms for reachability in surface-embedded graphs
  Derrick Stolee and N. V. Vinodchandran (University of Nebraska--Lincoln)


• Reductions Between Expansion Problems
  Prasad Raghavendra (Georgia Institute of Technology), David Steurer (Microsoft Research New England), Madhur Tulsiani (Toyota Technological Institute)


• On the Usefulness of Predicates
  Per Austrin (Toronto), Johan Hĺstad (KTH)


• Pseudorandom Generators for Read-Once ACC^0
  Dmitry Gavinsky (NEC Laboratories America, Inc.), Shachar Lovett (Institute of Advanced Study), Srikanth Srinivasan (DIMACS, Rutgers University)


• Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0-SAT
  Paul Beame (University of Washington), Russell Impagliazzo (Institute for Advanced Study and the University of California, San Diego), Srikanth Srinivasan (DIMACS, Rutgers University)


• The Hardness of Being Private
  Anil Ada (McGill University), Arkadev Chattopadhyay (University of Toronto), Stephen Cook (University of Toronto), Michal Koucký (Institute of Mathematics and Aarhus University), Lila Fontes (University of Toronto), Toniann Pitassi (University of Toronto).


• DNF Sparsification and Faster Deterministic Counting
  Parikshit Gopalan (Microsoft Research, SVC), Raghu Meka (Institute for Advanced Study, Princeton), Omer Reingold (Microsoft Research, SVC).


• Gaussian Noise Sensitivity and Fourier Tails
  Guy Kindler (Hebrew University of Jerusalem), Ryan O'Donnell (Carnegie Mellon University)


• Junto-symmetric functions, hypergraph isomorphism, and crunching
  Sourav Chakraborty (Chennai Mathematical Institute), Eldar Fischer (Technion), David García-Soriano (CWI, Amsterdam), Arie Matsliah (IBM Research, Haifa)


• Complexity Lower Bounds through Balanced Graph Properties
  Guy Moshkovitz (Tel Aviv University)


• Amplifying Circuit Lower Bounds Against Polynomial Time With Applications
  Richard J. Lipton (Georgia Institute of Technology), Ryan Williams (Stanford University)


• Space Complexity in Polynomial Calculus
  Yuval Filmus (University of Toronto), Massimo Lauria (Sapienza - University of Rome), Jakob Nordström (KTH Royal Institute of Technology), Neil Thapen (Institute of Mathematics, AS CR), Noga Zewi (Technion -- Israel Institute of Technology)