Computational Complexity Conference

CCC'15 - Accepted Papers

(In order of submission)

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

  • Verifiable stream computation and Arthur-Merlin communication
    Amit Chakrabarti (Dartmouth College), Graham Cormode (University of Warwick), Andrew McGregor (UMass Amherst), Justin Thaler (Yahoo Labs), Suresh Venkatasubramanian (University of Utah)

  • A polylogarithmic PRG for degree 2 threshold functions in the Gaussian setting
    Daniel Kane (University of California, San Diego)

  • The space complexity of cutting planes refutations
    Nicola Galesi (Sapienza University of Rome), Pavel Pudlák (Czech Academy of Sciences), Neil Thapen (Czech Academy of Sciences)

  • Circuits with medium fan-in
    Pavel Hrubes (Czech Academy of Sciences), Anup Rao (University of Washington)

  • Simplified lower bounds on the multiparty communication complexity of disjointness
    Anup Rao (University of Washington), Amir Yehudayoff (Technion)

  • Correlation bounds against monotone NC1
    Benjamin Rossman (National Institute of Informatics, Tokyo and Simons Institute, UC Berkeley)

  • Strong locally testable codes with relaxed local decoders
    Oded Goldreich (Weizmann Institute), Tom Gur (Weizmann Institute), Ilan Komargodski (Weizmann Institute)

  • On randomness extraction in AC0
    Oded Goldreich (Weizmann Institute), Emanuele Viola (Northeastern University and Harvard University), Avi Wigderson (Institute for Advanced Study)

  • Identifying an honest EXP^NP oracle among many
    Shuichi Hirahara (The University of Tokyo)

  • Adaptivity helps for testing juntas
    Rocco A. Servedio (Columbia University), Li-Yang Tan (Columbia University and Simons Institute, UC Berkeley), John Wright (Carnegie Mellon University)

  • Lower bounds for depth three arithmetic circuits with small bottom fanin
    Neeraj Kayal (Microsoft Research India), Chandan Saha (Indian Institute of Science)

  • Subexponential size hitting sets for bounded depth multilinear formulas
    Rafael Oliveira (Princeton University), Amir Shpilka (Tel-Aviv University), Ben Lee Volk (Tel-Aviv University)

  • On the (non) NP-hardness of computing circuit complexity
    Cody Murray (Stanford), Ryan Williams (Stanford)

  • Nonclassical polynomials as a barrier to polynomial lower bounds
    Abhishek Bhowmick (UT Austin), Shachar Lovett (UC San Diego)

  • Generalized quantum Arthur-Merlin games
    Hirotada Kobayashi (National Institute of Informatics), François Le Gall (The University of Tokyo), Harumichi Nishimura (Nagoya University)

  • Factors of polynomials of low individual degree
    Rafael Oliveira (Princeton University)

  • How to compress asymmetric communication
    Sivaramakrishnan Natarajan Ramamoorthy (University of Washington), Anup Rao (University of Washington)

  • The list-decoding size of Fourier-sparse Boolean functions
    Ishay Haviv (Academic College of Tel Aviv-Yaffo), Oded Regev (New York University)

  • Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
    Rohit Gurjar (IIT Kanpur), Arpita Korwar (IIT Kanpur), Nitin Saxena (IIT Kanpur), Thomas Thierauf (Hochschule Aalen)

  • A characterization of hard-to-cover CSPs
    Amey Bhangale (Rutgers University), Prahladh Harsha (Tata Institute of Fundamental Research), Girish Varma (Tata Institute of Fundamental Research)

  • Tight size-degree lower bounds for sums-of-squares proofs
    Massimo Lauria (KTH Royal Institute of Technology), Jakob Nordström (KTH Royal Institute of Technology)

  • A depth-five lower bound for iterated matrix multiplication
    Suman K. Bera (Dartmouth College), Amit Chakrabarti (Dartmouth College)

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

  • An entropy sumset inequality and polynomially fast convergence to Shannon capacity over all alphabets
    Venkatesan Guruswami (Carnegie Mellon University), Ameya Velingker (Carnegie Mellon University)

  • Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester
    Cedric Yen-Yu Lin (MIT), Han-Hsuan Lin (MIT)

  • Parallel repetition for entangled k-player games via fast quantum search
    Kai-Min Chung (Academia Sinica), Xiaodi Wu (MIT), Henry Yuen (MIT)

  • Majority is incompressible by AC^0[p] circuits
    Igor C. Oliveira (Columbia University), Rahul Santhanam (University of Edinburgh)

  • A generalized method for proving polynomial calculus degree lower bounds
    Mladen Miksa (KTH Royal Institute of Technology), Jakob Nordstrom (KTH Royal Institute of Technology)

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

Organized by:

Computational Complexity Foundation Inc.

Part of:

FCRC 2015

Sponsored by:

Microsoft Research

In Cooperation with:


Supported by: