The conference starts Wednesday July 15 in the morning, and ends on Saturday July 18 at 1 pm. The list of accepted papers can be found here.
Social events
There will be a conference dinner on Thursday 8PM at Macéo (15, rue des Petits Champs, Paris, 1st arrondissement). Extra tickets can be purchased at registration (subject to capacity constraints).Breakfast and lunch are not included. There are plenty of cafes, restaurants in the area near the conference site.
Preliminary program
| Wednesday 15/7 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 8:45-9:30 | Registration | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 9.30-12.30 | Chair: Johan Håstad
|
9.30-10.00 | Poly-logarithmic independence fools AC0 circuits
| Mark Braverman
10.00-10.30 | k-Subgraph Isomorphism on AC0 Circuits
| Kazuyuki Amano
10.30-11.00 | Break
|
11.00-11.30 | Fixed-Polynomial Size Circuit Bounds
| Lance Fortnow, Rahul Santhanam, Ryan Williams
11.30-12.00 | A new characterization of ACC0 and probabilistic CC0.
| Kristoffer Arnsfelt Hansen, Michal Koucký
12.00-12.30 | A Superpolynomial Lower Bound on the Size of Uniform
Non-constant-depth Threshold Circuits for the Permanent
| Pascal Koiran, Sylvain Perifel
12.30-14.30 | Lunch
|
14.30-17.30 | Chair: Ryan O'Donnell
|
14.30-15.00 | The Proof Complexity of Polynomial Identities
| Pavel Hrubes, Iddo Tzameret
15.00-15.30 | Locally Testable Codes Require Redundant Testers
| Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman
15.30-16.00 | Break
|
16.00-16.30 | Every Permutation CSP of arity 3 is Approximation Resistant
| Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran
16.30-17.00 | Inapproximability of Vertex Cover and Independent Set in Bounded
Degree Graphs
| Per Austrin, Subhash Khot, Muli Safra
17.00-17.30 | Are PCPs Inherent in Efficient Arguments
| Guy Rothblum, Salil Vadhan
Thursday 16/7
|
09.00-12.00 | Chair: Harry Buhrman
|
9.00-9.30 | Extractors for Low-Weight Affine Sources
| Anup Rao
9.30-10.00 | Extractors for varieties
| Zeev Dvir
10.00-10.30 | Break
|
10.30-11.00 | Weak derandomization of weak algorithms: explicit versions of
Yao's lemma
| Ronen Shaltiel
11.00-11.30 | Regularity, Boosting, and Efficiently Simulating Every High-Entropy
Distribution
| Luca Trevisan, Madhur Tulsiani, Salil Vadhan
11.30-12.00 | An Almost Optimal Rank Bound for Depth-3 Identities
| Nitin Saxena, C. Seshadri
12.00-14.00 | Lunch
|
14.00-17.30 | Chair: Anna Gál
|
14.00-14.30 | Lipschitz continuous ordinary differential equations are polynomial-
space complete
| Akitoshi Kawamura
14.30-15.00 | Improved Approximation of Linear Threshold Functions
| Ilias Diakonikolas, Rocco A. Servedio
15.00-15.30 | On the degree of Boolean functions in different characteristics.
| Parikshit Gopalan, Shachar Lovett, Amir Shpilka
15.30-16.00 | Break
|
16.00-16.30 | The complexity of the annihilating polynomial
| Neeraj Kayal
16.30-17.00 | One-Way Functions and the Isomorphism Conjecture
| Manindra Agrawal, Osamu Watanabe
17.00-17.30 | Planar Graph Isomorphism is in Log-Space
| Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
| 20.00 Conference dinner at Macéo
Friday 17/7
|
9.00-12.00 | Chair: Oded Regev
|
9.00-9.30 | Oracularization and Two-Prover One-Round Interactive Proofs
against Nonlocal Strategies
| Tsuyoshi Ito, Hirotada Kobayashi, Keiji Matsumoto
09.30-10.00 | Quantum Copy-Protection and Quantum Money
| Scott Aaronson
10.00-10.30 | Break
|
10.30-11.00 | Parallel approximation of non-interactive zero-sum quantum
games
| Rahul Jain, John Watrous
11.00-11.30 | Lower bounds on quantum multiparty communication complexity
| Troy Lee, Gideon Schechtman, Adi Shraibman
11.30-12.00 | Increasing the gap between Descriptional Complexity and Algorithmic
Probability
| Adam R. Day
12.00-14.00 | Lunch
|
14.00-17.30 | Chair: Johan Håstad
|
14.00-14.30 | Reconstruction of Generalized Depth-3 Arithmetic Circuits
with Bounded Top Fan-in
| Zohar S. Karnin, Amir Shpilka
14.30-15.00 | Multitask Efficiencies in the Decision Tree Model
| Andrew Drucker
15.00-15.30 | Break
|
15.30-16.00 | Worst-Case Running Times for Average-Case Algorithms
| Luis Antunes, Lance Fortnow
16.00-16.30 | On basing ZK ≠ BPP on the hardness of PAC learning
| David Xiao
16.30-17.00 | Infinite vs. Finite Space-Bounded Randomized Computations
| Richard Kralovic
| 17.15-19.00 Business meeting
Saturday 18/7
|
9.00-12.30 | Chair: Harry Buhrman
|
9.00-9.30 | Communication Complexity of Read Once AC0 Formulae
| T.S. Jayram, Swastik Kopparty, Prasad Raghavendra
9.30-10.00 | Lower bounds on the randomized communication complexity of
read-once functions
| Nikos Leonardos, Michael Saks
10.00-10.30 | An approximation algorithm for approximation rank
| Troy Lee, Adi Shraibman
10.30-11.00 | Break
|
11.00-11.30 | A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences
| Joshua Brody, Amit Chakrabarti
11.30-12.00 | New Results in the Simultaneous Message Passing Model
| Rahul Jain, Hartmut Klauck
12.00-12.30 | The Maximum Communication Complexity of Multi-party Pointer Jumping
| Joshua Brody | |||||