On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofsNathan SegerlindExponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication ComplexityDmitry Gavinsky and Pavel PudlákTowards Dimension Expanders Over Finite FieldsZeev Dvir and Amir ShpilkaUsing Entanglement in Quantum Multi-Prover Interactive ProofsJulia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Thomas VidickCommunication Complexity Under Product and Nonproduct DistributionsAlexander A. SherstovApproximate Inclusion-Exclusion for Arbitrary Symmetric FunctionsAlexander A. SherstovAmplifying ZPPRichard Chang and Suresh Purini^{SAT[1]}and the Two Queries ProblemAmplifying Lower Bounds by Means of Self-ReducibilityEric Allender and Michal KouckýBlack Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-inZohar S. Karnin and Amir ShpilkaThe sum of d small-bias generators fools polynomials of degree dEmanuele ViolaLearning complexity vs. communication complexityNathan Linial and Adi ShraibmanLocally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne NumbersKiran S. Kedlaya and Sergey YekhaninA direct product theorem for discrepancyTroy Lee, Adi Shraibman, and Robert ŠpalekThe Multiplicative Quantum AdversaryRobert ŠpalekDisjointness is hard in the multi-party number-on-the-forehead modelTroy Lee and Adi ShraibmanGeneralized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof SystemsTsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, and Andrew C.-C. YaoApproximisation of natural W[P]-complete minimisation problems is hardKord Eickmeyer, Martin Grohe, and Magdalena GrüberNoisy Interpolating Sets for Low Degree PolynomialsZeev Dvir and Amir ShpilkaApproximation Resistant Predicates From Pairwise IndependencePer Austrin and Elchanan MosselNew results on Noncommutative and Commutative Polynomial Identity TestingV. Arvind, Partha Mukhopadhyay, and Srikanth SrinivasanQuantum Expanders: Motivation and ConstructionsAvraham Ben-Aroya, Oded Schwartz, and Amnon Ta-ShmaRandomized Individual Communication ComplexityHarry Buhrman, Michal Koucký, and Nikolai Vereshchagin2-Transitivity is Insufficient for Local TestabilityElena Grigorescu, Tali Kaufman, and Madhu SudanSoft decoding, dual BCH codes, and better epsilon-biased list-decodable codesVenkatesan Guruswami and Atri RudraHardness amplification within NP against deterministic algorithmsParikshit Gopalan and Venkatesan GuruswamiConstraint Logic: A Uniform Framework for Modeling Computation as GamesErik D. Demaine and Robert A. HearnLower Bounds and Separations for Constant Depth Multilinear CircuitsRan Raz and Amir YehudayoffDetecting Rational Points on Hypersurfaces over Finite FieldsSwastik Kopparty and Sergey YekhaninNP-hard sets are exponentially dense unless coNP is contained in NP/polyHarry Buhrman and John M. HitchcockThe Power of UnentanglementScott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter ShorConstant Width Planar Branching Programs Characterize ACCKristoffer Arnsfelt Hansen^{0}in Quasipolynomial SizeThe quantum moment problem and bounds on entangled multiprover gamesAndrew C. Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie WehnerA Hypergraph Long Code Test with Perfect CompletenessVictor Chen