IEEE Conference on Computational Complexity

July 15th to July 18th, 2009
Paris, France

Local arrangements

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

PDF version

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


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


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