**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)

Part of:

FCRC 2015