CCC 2013: Program

The list of accepted papers, with abstracts, can be found here.

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

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

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

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