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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
19.00-21.00 | Welcome reception & registration
Tuesday June 26, 2012
|
8:30-9:00 | Registration
|
9.00-12.00
| Morning Sessions
|
9.00-9.30 | Amplifying 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.00-10.30 | Break
|
10.30-11.00 | 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)
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.)
12.00-14.00 | Lunch |
14.00-17.00 | Afternoon 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)
| 17.00- 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.00 | Invited 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).
| 18.00- 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.00 | Invited 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) | ||||||