CCC 2013: Program
- Regular talks are on June 5, June 6, and June 7.
- The talks for award papers start at 1:30pm on June 5.
- The rump session starts at 5:30pm on June 5.
- An invited talk by Ronald de Wolf is at 11:00am on June 6.
- The business meeting is at 8:30pm on June 6.
- An invited talk by Zeev Dvir is at 11:00am on June 7.
Online Proceedings: Click the titles of the papers
below to view the paper. You will be prompted for a username and password.
These were sent by email to all those registered for the conference.
Those registered may also download the entire proceedings
here.
Wednesday June 5
| Time | Talk/Event |
|---|---|
| 8:15 | Breakfast |
| 9:00 |
Random Arithmetic Formulas can be Reconstructed Efficiently
Ankit Gupta (Microsoft Research India), Neeraj Kayal (Microsoft Research India), Youming Qiao (National University of Singapore) |
| 9:30 |
Formulas are Exponentially Stronger than Monotone Circuits in Non-Commutative Setting Pavel Hrubes (University of Washington), Amir Yehudayoff (Technion) |
| 10:00 |
On Medium-Uniformity and Circuit Lower Bounds Rahul Santhanam (University of Edinburgh), Ryan Williams (Stanford University) |
| 10:30 | Break |
| 11:00 |
Towards a Reverse Newman's Theorem in Interactive Information Complexity Joshua Brody (Aarhus University), Harry Buhrman (CWI and University of Amsterdam), Michal Koucky (Czech Academy of Sciences), Bruno Loff (CWI), Florian Speelman (CWI), Nikolay Vereshchagin (Moscow State University) |
| 11:30 |
Shared Randomness and Quantum Communication in the Multi-Party Model Dmitry Gavinsky (NEC Laboratories America), Tsuyoshi Ito (NEC Laboratories America), Guoming Wang (NEC Laboratories America and UC Berkeley) |
| 12:00 | Lunch |
| Award Papers | |
| 1:30 |
On the Power of Non-Adaptive Learning Graphs Aleksandrs Belovs (University of Latvia), Ansis Rosmanis (University of Waterloo.) |
| 2:00 |
The Correct Exponent for the Gotsman-Linial Conjecture Daniel Kane (Stanford University) |
| 2:30 |
Approaching the Chasm at Depth Four Ankit Gupta (Microsoft Research India), Pritish Kamath (Microsoft Research India), Neeraj Kayal (Microsoft Research India), Ramprasad Saptharishi (Chennai Mathematical Institute) |
| 3:00 | Break |
| 3:30 |
Approximating Boolean Functions with Depth-2 Circuits Eric Blais (MIT), Li-Yang Tan (Columbia University) |
| 4:00 |
Constructing Hard Functions from Learning Algorithms Adam Klivans (University of Texas at Austin), Pravesh Kothari (University of Texas at Austin), Igor C. Oliveira (Columbia University) |
| 4:30 |
Short Lists with Short Programs in Short Time Bruno Bauwens (Université de Lorraine), Anton Makhlin (Moscow State University), Nikolay Vereshchagin (Moscow State University), Marius Zimand (Towson University) |
| 5:00 | Break |
| 5:30 | Rump Session |
| 7:00 | End of Talks |
Thursday June 6
| Time | Talk/Event |
|---|---|
| 8:15 | Breakfast |
| 9:00 |
Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle Albert Atserias (UPC, Barcelona), Moritz Müller (Kurt Gödel Research Center, Vienna), Sergi Oliva (UPC, Barcelona) |
| 9:30 |
LS+ Lower Bounds from Pairwise Independence Madhur Tulsiani (TTI Chicago), Pratik Worah (University of Chicago) |
| 10:00 |
Just a Pebble Game Siu Man Chan (UC Berkeley) |
| 10:30 | Break |
| 11:00 | Invited Talk:
Quantum Proofs for Classical Theorems Ronald de Wolf (CWI and University of Amsterdam) |
| 12:00 | Lunch |
| 1:30 |
Quantum XOR Games Oded Regev (Courant Institute), Thomas Vidick (MIT) |
| 2:00 |
Two-message Quantum Interactive Proofs and the Quantum Separability Problem Patrick Hayden (McGill University), Kevin Milner (McGill University), Mark Wilde (McGill University) |
| 2:30 |
Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits Yasuhiro Takahashi (NTT Communication Science Laboratories), Seiichiro Tani (NTT Communication Science Laboratories) |
| 3:00 | Break |
| 3:30 |
How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions? Andris Ambainis (University of Latvia), Ronald de Wolf (CWI and University of Amsterdam) |
| 4:00 |
Composition Limits and Separating examples for Some Boolean Function Complexity Measures Justin Gilmer (Rutgers University), Michael Saks (Rutgers University), Srikanth Srinivasan (IIT Bombay) |
| 4:30 |
On Rigid Matrices and U-Polynomials Noga Alon (Tel-Aviv University), Gil Cohen (Weizmann Institute of Science) |
| 5:00 | End of Talks |
| 8:30 | Business Meeting |
Friday June 7
| Time | Talk/Event |
|---|---|
| 8:15 | Breakfast |
| 9:00 |
Covering CSPs Irit Dinur (Weizmann Institute), Gillat Kol (Weizmann Institute) |
| 9:30 |
Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover Sushant Sachdeva (Princeton University), Rishi Saket (IBM Research) |
| 10:00 |
On the Lattice Smoothing Parameter Problem Kai-Min Chung (Cornell University), Daniel Dadush (New York University), Feng-Hao Liu (Brown University), Chris Peikert (Georgia Institute of Technology) |
| 10:30 | Break |
| 11:00 | Invited Talk:
Incidence Theorems and Their Applications Zeev Dvir (Princeton) |
| 12:00 | Lunch |
| 1:30 |
A Derandomized Switching Lemma and an Improved Derandomization of AC0 Luca Trevisan (Stanford University), TongKe Xue (Stanford University) |
| 2:00 |
The Distinguishability of Product Distributions by Read-Once Branching Programs John Steinberger (Tsinghua University) |
| 2:30 |
Strong LTCs with Inverse Polylogarithmic Rate and Soundness Michael Viderman (Technion) |
| 3:00 | Break |
| 3:30 |
On the Parameterized and Approximation Hardness of Metric Dimension Sepp Hartung (TU Berlin), André Nichterlein (TU Berlin) |
| 4:00 |
An O(n^{1/2+epsilon}) Space Algorithm for Directed Planar Reachability with Polynomial Running Time T. Imai (Tokyo Institute of Technology), K. Nakagawa (Tokyo Institute of Technology), A. Pavan (Iowa State University), N. V. Vinodchandran (University of Nebraska-Lincoln), O. Watanabe (Tokyo Institute of Technology) |
| 4:30 |
Superlinear Lower Bounds for Multipass Graph Processing Venkatesan Guruswami (CMU), Krzysztof Onak (IBM Research) |
| 5:00 | End of Talks/Conference |