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)