27th IEEE Conference on Computational Complexity

June 26th to 29th, 2012
Porto, Portugal

The conference will start Tuesday, June 26, in the morning, and end on Friday, June 29, at 12.30pm. The list of accepted papers can be found here.

Preliminary program

Monday June 25, 2012


Welcome reception & registration

Tuesday June 26, 2012
8:30-9:00 Registration
9.00-12.00 Morning Sessions
9.00-9.30Amplifying Circuit Lower Bounds Against Polynomial Time With Applications
Richard J. Lipton (Georgia Institute of Technology), Ryan Williams (Stanford University)
9.30-10.00 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).
10.30-11.00Parallel approximation of min-max problems with applications to classical and quantum zero-sum games
Gus Gutoski (University of Waterloo), Xiaodi Wu (University of Michigan)
11.00-11.30 The Complexity of the Separable Hamiltonian Problem
André Chailloux (UC Berkeley, California), Or Sattath (Hebrew University of Jerusalem)
11.30-12.00 Quantum Money with Classical Verification
Dmitry Gavinsky (NEC Laboratories America, Inc.)

14.00-17.00Afternoon Sessions
14.00-14.30 On the Usefulness of Predicates
Per Austrin (Toronto), Johan Håstad (KTH)
14.30-15.00 Reductions Between Expansion Problems
Prasad Raghavendra (Georgia Institute of Technology), David Steurer (Microsoft Research New England), Madhur Tulsiani (Toyota Technological Institute)
15.00-15.30 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)
15.30-16.00 Break
16.00-16.30 Testing List H-Homomorphisms
Yuichi Yoshida (Kyoto University and Preferred Infrastructure, Inc.)
16.30-17.00 A Dichotomy for Real Weighted Holant Problems
Sangxia Huang (KTH Royal Institute of Technology), Pinyan Lu (Microsoft Research Asia)


Port outing
Wednesday June 27, 2012
09.00-12.00 Morning Sessions
9.00-9.30 A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis
Kazuhisa Seto and Suguru Tamaki (Kyoto University)
9.30-10.00 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)
10.00-10.30 DNF Sparsification and Faster Deterministic Counting
Parikshit Gopalan (Microsoft Research, SVC), Raghu Meka (Institute for Advanced Study, Princeton), Omer Reingold (Microsoft Research, SVC).
10.00-10.30 Break
11.00-12.00Invited Talk: Communication Complexity and Information Cost: Foundations and New Directions
Toniann Pitassi (University of Toronto)
12.00-14.00 Lunch
14.00-17.30 Afternoon Sessions
14.00-14.30 Gaussian Noise Sensitivity and Fourier Tails
Guy Kindler (Hebrew University of Jerusalem), Ryan O'Donnell (Carnegie Mellon University)
14.30-15.00 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)
15.00-15.30 Complexity Lower Bounds through Balanced Graph Properties
Guy Moshkovitz (Tel Aviv University)
15.30-16.00 Break
16.00-16.30 Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators
Andrew Drucker (MIT)
16.30-17.00 Limits on Alternation-Trading Proofs for Time-Space Lower Bounds
Samuel R. Buss (University of California, San Diego), Ryan Williams (Stanford University)
17.00-17.30 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).


Business meeting

Thursday June 28, 2012
09.00-12.00 Morning Sessions
9.00-9.30 Matrix Lie Algebra Isomorphism
Joshua A. Grochow (The University of Chicago)
9.30-10.00 On sunflowers and matrix multiplication
Noga Alon (Tel Aviv University), Amir Shpilka (Technion), Christopher Umans (Caltech)
10.00-10.30 Algebras of minimal multiplicative complexity
Markus Bläser (Saarland University), Bekhan Chokaev (Moscow State University)
10.00-10.30 Break
11.00-12.00Invited Talk: Prospects for Geometric Complexity Theory
Peter Bürgisser (Universität Paderborn)
12.00-14.00 Lunch
14.00-17.30 Afternoon Sessions
14.00-14.30 A strong direct product theorem for quantum query complexity
Troy Lee (Centre for Quantum Technologies), Jérémie Roland (Université Libre de Bruxelles)
14.30-15.00 A Strong Parallel Repetition Theorem for Projection Games on Expanders
Ran Raz (Weizmann Institute), Ricky Rosen (Princeton University)
15.00-15.30 Share Conversion and Private Information Retrieval
Amos Beimel (Ben-Gurion University), Yuval Ishai (Technion), Eyal Kushilevitz (Technion), Ilan Orlov (Ben-Gurion University)
15.30-16.00 Break
16.00-16.30 Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games
Baris Aydinlioglu (University of Wisconsin-Madison), Dieter van Melkebeek (University of Wisconsin-Madison)
16.30-17.00 Hitting Set Generators for Sparse Polynomials over any Finite Fields
Chi-Jen Lu (Academia Sinica)
17.00-17.30 Pseudorandom Generators for Read-Once ACC^0
Dmitry Gavinsky (NEC Laboratories America, Inc.), Shachar Lovett (Institute of Advanced Study), Srikanth Srinivasan (DIMACS, Rutgers University)
Friday June 29, 2012
9.00-12.30 Morning Sessions
9.00-9.30 Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification
Gil Cohen and Ran Raz (Weizmann Institute), Gil Segev (MSR Silicon Valley)
9.30-10.00 Better condensers and new extractors from Parvaresh-Vardy codes
Amnon Ta-Shma (Tel-Aviv University), Christopher Umans (Caltech)
10.00-10.30 List Decoding Barnes-Wall Lattices
Elena Grigorescu and Chris Peikert (Georgia Institute of Technology)
10.30-11.00 Break
11.00-11.30 Space-efficient algorithms for reachability in surface-embedded graphs
Derrick Stolee and N. V. Vinodchandran (University of Nebraska--Lincoln)
11.30-12.00 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)
12.00-12.30 Combinatorial PCPs with Short Proofs
Or Meir (Stanford University)