IEEE Conference on Computational Complexity 2012 (CCC'12)

June 26
• Richard J. Lipton and Ryan Williams: Amplifying Circuit Lower Bounds Against Polynomial Time With Applications

• Holger Dell , Valentine Kabanets , Dieter van Melkebeek , Osamu Watanabe: Is the Valiant-Vazirani Isolation Lemma Improvable?

• Gus Gutoski, Xiaodi Wu: Parallel approximation of min-max problems with applications to classical and quantum zero-sum games

• André Chailloux, Or Sattath: The Complexity of the Separable Hamiltonian Problem

• Dmitry Gavinsky: Quantum Money with Classical Verification

• Per Austrin, Johan Håstad: On the Usefulness of Predicates

• Prasad Raghavendra , David Steurer, Madhur Tulsiani: Reductions Between Expansion Problems

• Marek Cygan, Holger Dell, Daniel Lokshtanov, Daniel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlstrom: On Problems as Hard as CNFSAT

• Yuichi Yoshida: Testing List H-Homomorphisms

• Sangxia Huang, Pinyan Lu: A Dichotomy for Real Weighted Holant Problems

June 27
• Kazuhisa Seto and Suguru Tamaki: A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

• Paul Beame, Russell Impagliazzo, Srikanth Srinivasan: Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0-SAT

• Parikshit Gopalan, Raghu Meka, Omer Reingold: DNF Sparsification and Faster Deterministic Counting

• Toniann Pitassi:Communication Complexity and Information Cost: Foundations and New Directions

• Guy Kindler, Ryan O'Donnell: Gaussian Noise Sensitivity and Fourier Tails

• Sourav Chakraborty, Eldar Fischer, David García-Soriano, Arie Matsliah: Junto-symmetric functions, hypergraph isomorphism, and crunching

• Guy Moshkovitz: Complexity Lower Bounds through Balanced Graph Properties

• Andrew Drucker: Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators

• Samuel R. Buss, Ryan Williams: Limits on Alternation-Trading Proofs for Time-Space Lower Bounds

• Anil Ada, Arkadev Chattopadhyay, Stephen Cook, Michal Koucký , Lila Fontes, Toniann Pitassi: The Hardness of Being Private

June 28
• Joshua A. Grochow: Matrix Lie Algebra Isomorphism

• Noga Alon, Amir Shpilka, Christopher Umans: On sunflowers and matrix multiplication

• Markus Bläser, Bekhan Chokaev: Algebras of minimal multiplicative complexity

• Peter Bürgisser: Prospects for Geometric Complexity Theory

• Troy Lee, Jérémie Roland: A strong direct product theorem for quantum query complexity

• Ran Raz, Ricky Rosen: A Strong Parallel Repetition Theorem for Projection Games on Expanders

• Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Ilan Orlov: Share Conversion and Private Information Retrieval

• Baris Aydinlioglu, Dieter van Melkebeek: Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games

• Chi-Jen Lu: Hitting Set Generators for Sparse Polynomials over any Finite Fields

• Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan: Pseudorandom Generators for Read-Once ACC^0

June 29
• Gil Cohen and Ran Raz, Gil Segev: Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification

• Amnon Ta-Shma, Christopher Umans:Better condensers and new extractors from Parvaresh-Vardy codes

• Elena Grigorescu and Chris Peikert: List Decoding Barnes-Wall Lattices

• Derrick Stolee and N. V. Vinodchandran: Space-efficient algorithms for reachability in surface-embedded graphs

• Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, Noga Zewi Space: Complexity in Polynomial Calculus

• Or Meir: Combinatorial PCPs with Short Proofs