Computational Complexity Conference

CCC'15 - Program

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.

Wednesday June 17

8:15 AMBreakfast
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 AMCoffee break
11:20 AM FCRC keynote lecture

Don Syme (Microsoft Research Cambridge)

12:30 PMLunch
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 PMCoffee 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

Factors of low individual degree polynomials (abstract)

Rafael Oliveira (Princeton University)

5:45 PMDinner (on your own)
8:30 PMBusiness meeting

Thursday June 18

8:15 AMBreakfast
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 AMCoffee break
11:20 AM FCRC keynote lecture

Kathy Yelick (UC Berkeley)

12:30 PMLunch
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 PMCoffee 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

Correlation bounds against monotone NC1 (abstract)

Benjamin Rossman (NII, Tokyo and Simons Institute, UC Berkeley)

5:45 PMDinner (on your own)
8:30 PMRump session

Friday June 19

8:15 AMBreakfast
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 AMCoffee break
11:20 AM FCRC keynote lecture

Balaji Prabhakar (Stanford)

12:30 PMLunch
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 PMCoffee 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 PMEnd of the conference

Organized by:

Computational Complexity Foundation Inc.

Part of:

FCRC 2015

Sponsored by:

Microsoft Research

In Cooperation with:

EATCS

Supported by:

IQC