**Schedule**
Each day has a morning session of four talks 9-11 and two afternoon sessions of three talks, 2-3:30 and 4-5:30 or 4-5:45. All talks are 30 minutes except those for the best paper and best student paper award winners, which are 45 minutes.
There is also
an FCRC plenary talk each day 11:20-12:30. In addition, there is a business
meeting the first evening and a rump session the second evening, each
starting at 8:30.

**Location**
All talks/events specific to CCC'15 take place in
room
B117-B119 of the Oregon Convention Center.

**Online Proceedings**
Click the title of a paper in the program to view the full paper, and
the word "abstract"
to show or hide the abstract.
You may also download
the complete Proceedings of CCC'15,
as published with open access by the Leibniz International Proceedings in Informatics (LIPIcs).

**Slides**
Click the word "slides" in the program to see the presentations
that the authors agreed to post on this website.

8:15 AM | Breakfast |

9:00 AM |
Strong locally testable codes with relaxed local decoders (abstract) Oded Goldreich (Weizmann Institute), Tom Gur (Weizmann Institute), Ilan Komargodski (Weizmann Institute) |

9:30 AM |
An entropy sumset inequality and polynomially fast convergence to Shannon capacity over all alphabets (abstract) Venkatesan Guruswami (Carnegie Mellon University), Ameya Velingker (Carnegie Mellon University) |

10:00 AM |
The list-decoding size of Fourier-sparse Boolean functions (abstract) Ishay Haviv (Academic College of Tel Aviv-Yaffo), Oded Regev (New York University) |

10:30 AM |
Nonclassical polynomials as a barrier to polynomial lower bounds (abstract) Abhishek Bhowmick (UT Austin), Shachar Lovett (UC San Diego) |

11:00 AM | Coffee break |

11:20 AM |
FCRC keynote lecture
Don Syme (Microsoft Research Cambridge) |

12:30 PM | Lunch |

2:00 PM |
Simplified lower bounds on the multiparty communication complexity of disjointness (abstract) Anup Rao (University of Washington), Amir Yehudayoff (Technion) |

2:30 PM |
How to compress asymmetric communication (abstract) Sivaramakrishnan Natarajan Ramamoorthy (University of Washington), Anup Rao (University of Washington) |

3:00 PM |
Majority is incompressible by AC^0[p] circuits (abstract) Igor C. Oliveira (Columbia University), Rahul Santhanam (University of Edinburgh) |

3:30 PM | Coffee break |

4:00 PM |
Lower bounds for depth three arithmetic circuits with small bottom fanin (abstract, slides) Neeraj Kayal (Microsoft Research India), Chandan Saha (Indian Institute of Science) |

4:30 PM |
A depth-five lower bound for iterated matrix multiplication (abstract) Suman K. Bera (Dartmouth College), Amit Chakrabarti (Dartmouth College) |

5:00 PM |
Best student paper award winner
Rafael Oliveira (Princeton University) |

5:45 PM | Dinner (on your own) |

8:30 PM | Business meeting |

8:15 AM | Breakfast |

9:00 AM |
Verifiable stream computation and Arthur-Merlin communication (abstract, slides) Amit Chakrabarti (Dartmouth College), Graham Cormode (University of Warwick), Andrew McGregor (UMass Amherst), Justin Thaler (Yahoo Labs), Suresh Venkatasubramanian (University of Utah) |

9:30 AM |
Identifying an honest EXP^NP oracle among many (abstract, slides) Shuichi Hirahara (The University of Tokyo) |

10:00 AM |
Adaptivity helps for testing juntas (abstract) Rocco A. Servedio (Columbia University), Li-Yang Tan (Columbia University / Simons Institute, UC Berkeley), John Wright (Carnegie Mellon University) |

10:30 AM |
A characterization of hard-to-cover CSPs (abstract) Amey Bhangale (Rutgers University), Prahladh Harsha (Tata Institute of Fundamental Research), Girish Varma (Tata Institute of Fundamental Research) |

11:00 AM | Coffee break |

11:20 AM |
FCRC keynote lecture
Kathy Yelick (UC Berkeley) |

12:30 PM | Lunch |

2:00 PM |
Subexponential size hitting sets for bounded depth multilinear formulas (abstract) Rafael Oliveira (Princeton University), Amir Shpilka (Tel-Aviv University), Ben Lee Volk (Tel-Aviv University) |

2:30 PM |
Deterministic identity testing for sum of read-once oblivious arithmetic branching programs (abstract, slides) Rohit Gurjar (IIT Kanpur), Arpita Korwar (IIT Kanpur), Nitin Saxena (IIT Kanpur), Thomas Thierauf (Hochschule Aalen) |

3:00 PM |
Kolmogorov width of discrete linear spaces: an approach to matrix rigidity (abstract,
slides) Alex Samorodnitsky (Hebrew University), Ilya Shkredov (Steklov Mathematical Institute and IITP RAS), Sergey Yekhanin (Microsoft) |

3:30 PM | Coffee break |

4:00 PM |
On the (non) NP-hardness of computing circuit complexity (abstract) Cody Murray (Stanford), Ryan Williams (Stanford) |

4:30 PM |
Circuits with medium fan-in (abstract) Pavel Hrubes (Czech Academy of Sciences), Anup Rao (University of Washington) |

5:00 PM |
Best paper award winner
Benjamin Rossman (NII, Tokyo and Simons Institute, UC Berkeley) |

5:45 PM | Dinner (on your own) |

8:30 PM | Rump session |

8:15 AM | Breakfast |

9:00 AM |
Non-commutative formulas and Frege lower bounds: a new characterization of propositional proofs (abstract) Fu Li (Tsinghua University), Iddo Tzameret (Royal Holloway, University of London), Zhengyu Wang (Harvard University) |

9:30 AM |
The space complexity of cutting planes refutations (abstract, slides) Nicola Galesi (Sapienza University of Rome), Pavel Pudlák (Czech Academy of Sciences), Neil Thapen (Czech Academy of Sciences) |

10:00 AM |
Tight size-degree lower bounds for sums-of-squares proofs (abstract, slides) Massimo Lauria (KTH Royal Institute of Technology) Jakob Nordström (KTH Royal Institute of Technology) |

10:30 AM |
A generalized method for proving polynomial calculus degree lower bounds (abstract, slides) Mladen Miksa (KTH Royal Institute of Technology), Jakob Nordstrom (KTH Royal Institute of Technology) |

11:00 AM | Coffee break |

11:20 AM |
FCRC keynote lecture
Balaji Prabhakar (Stanford) |

12:30 PM | Lunch |

2:00 PM |
Generalized quantum Arthur-Merlin games (abstract, slides) Hirotada Kobayashi (National Institute of Informatics), François Le Gall (University of Tokyo), Harumichi Nishimura (Nagoya University) |

2:30 PM |
Parallel repetition for entangled k-player games via fast quantum search (abstract) Kai-Min Chung (Academia Sinica), Xiaodi Wu (MIT), Henry Yuen (MIT) |

3:00 PM |
Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester (abstract, slides) Cedric Yen-Yu Lin (MIT), Han-Hsuan Lin (MIT) |

3:30 PM | Coffee break |

4:00 PM |
A polylogarithmic PRG for degree 2 threshold functions in the Gaussian setting (abstract) Daniel Kane (University of California, San Diego) |

4:30 PM |
Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (abstract) Benny Applebaum (Tel-Aviv University), Sergei Artemenko (University of Haifa), Ronen Shaltiel (University of Haifa), Guang Yang (Tsinghua University) |

5:00 PM |
On randomness extraction in AC0 (abstract) Oded Goldreich (Weizmann Institute), Emanuele Viola (Northeastern University and Harvard University), Avi Wigderson (Institute for Advanced Study) |

5:30 PM | End of the conference |

Part of:

FCRC 2015