- Ran Raz:
**Elusive Functions and Lower Bounds for Arithmetic Circuits.**

- Arkadev Chattopadhyay, Anil Ada:
**Multiparty Communication Complexity of Disjointness.**

- Troy Lee, Adi Shraibman:
**Disjointness is hard in the multi-party number-on-the-forehead model.**

- Zeev Dvir, Amir Shpilka:
**Noisy Interpolating Sets for Low Degree Polynomials.**

- Scott Aaronson, Avi Wigderson:
**Algebrization: A New Barrier in Complexity Theory.**

- Ran Raz, Amir Yehudayoff:
**Lower Bounds and Separations for Constant Depth Multilinear Circuits.**

- Dan Gutfreund, Salil P. Vadhan:
**Limitations of Hardness vs. Randomness under Uniform Reductions.**

- Venkatesan Guruswami, Prasad Raghavendra:
**Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness.**

- Per Austrin, Elchanan Mossel:
**Approximation Resistant Predicates From Pairwise Independence.**

- Itai Benjamini, Oded Schramm, Asaf Shapira:
**Every Minor-Closed Property of Sparse Graphs is Testable.**

- Kazuo Iwama, Suguru Tamaki:
**The Complexity of the Hajos Calculus for Planar Graphs.**

- Arnab Bhattacharyya:
**A Note on the Distance to Monotonicity of Boolean Functions.**

- Anup Rao:
**Parallel Repetition in Projection Games and a Concentration Bound.**

- Matei David, Toniann Pitassi:
**Separating NOF communication complexity classes RP and NP.**

- Anup Rao:
**Extractors for Low-Weight Affine Sources.**

- Alexander A. Razborov, Alexander A. Sherstov:
**The Sign-Rank of AC^0.**

- Dieter van Melkebeek, Thomas Watson:
**A Quantum Time-Space Lower Bound for the Counting Hierarchy.**

- Ran Raz:
**A Counterexample to Strong Parallel Repetition.**

- Stasys Jukna:
**Entropy of operators or why matrix multiplication is hard for small depth circuits.**

- Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan:
**Decodability of Group Homomorphisms beyond the Johnson Bound.**

- Shankar Kalyanaraman, Christopher Umans:
**The Complexity of Rationalizing Matchings.**

- Harry Buhrman, John M. Hitchcock:
**NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly.**

- Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi:
**Fast Integer Multiplication using Modular Arithmetic.**

- Paul Beame, Dang-Trinh Huynh-Ngoc:
**On the Value of Multiple Read/Write Streams for Approximating Frequency Moments.**

- Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan:
**New results on Noncommutative and Commutative Polynomial Identity Testing.**

- Jakob Nordström, Johan Håstad:
**Towards an Optimal Separation of Space and Length in Resolution.**

- Till Tantau:
**Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets.**

- Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer:
**The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments.**

- Christian Glaßer, Christian Reitwießner, Victor L. Selivanov:
**The Shrinking Property for NP and coNP.**

- Bruno Durand, Alexander Shen, Andrei E. Romashchenko:
**Fixed Point and Aperiodic Tilings.**

- James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers:
**Computability and Complexity in Self-Assembly.**

- Dmitriy Yu. Cherukhin:
**Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates.**

- Elena Grigorescu, Tali Kaufman, Madhu Sudan:
**2-Transitivity is Insufficient for Local Testability.**

- Dan Gutfreund, Guy N. Rothblum:
**The Complexity of Local List Decoding.**

- James I. Lathrop, Jack H. Lutz, Scott M. Summers:
**Strict Self-Assembly of Discrete Sierpinski Triangles.**

- Venkatesan Guruswami, Atri Rudra:
**Soft decoding, dual BCH codes, and better list-decodable eps-biased codes.**

- Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo:
**Curves That Must Be Retraced.**

- Eric Allender, Michal Koucký:
**Amplifying Lower Bounds by Means of Self-Reducibility.**

- Oded Goldreich, Dana Ron:
**Algorithmic Aspects of Property Testing in the Dense Graphs Model.**

- Sourav Chakraborty, László Babai:
**Property Testing of Equivalence under a Permutation Group Action.**

- Oded Goldreich, Dana Ron:
**On Proximity Oblivious Testing.**

- Zeev Dvir:
**Deterministic Extractors for Algebraic Sources.**

- Gábor Ivanyos, Marek Karpinski, Nitin Saxena:
**Schemes for Deterministic Polynomial Factoring.**

- Miki Hermann, Reinhard Pichler:
**Complexity of Counting the Optimal Solutions.**

- Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
**Dense Subsets of Pseudorandom Sets.**

- Nikhil R. Devanur, Lance Fortnow:
**A Computational Theory of Awareness and Decision Making.**

- Vijay V. Vazirani, Wang Lei:
**Continuity Properties of Equilibria in Some Fisher and Arrow-Debreu Market Models.**

- Meena Mahajan, B. V. Raghavendra Rao:
**Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae.**

- Vikraman Arvind, Partha Mukhopadhyay:
**Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size.**

- Manoj Prabhakaran, Mike Rosulek:
**Cryptographic Complexity of Multi-party Computation Problems: Classifications and Separations.**

- Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor:
**The Power of Unentanglement.**

- Vikraman Arvind, T. C. Vijayaraghavan:
**The Orbit problem is in the GapL Hierarchy.**

- Stephen A. Fenner, William I. Gasarch, Brian Postow:
**The complexity of learning SUBSEQ(A).**

- Venkatesan Guruswami, Atri Rudra:
**Concatenated codes can achieve list-decoding capacity.**

- Ryan O'Donnell:
**Some Topics in Analysis of Boolean Functions.**

- Beate Bollig:
**On the OBDD complexity of the most significant bit of integer multiplication.**

- Alexander A. Sherstov:
**Communication Lower Bounds Using Dual Polynomials.**

- Zeev Dvir, Avi Wigderson:
**Kakeya sets, new mergers and old extractors.**

- Farid M. Ablayev, Alexander Vasiliev:
**On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting.**

- James R. Lee, Prasad Raghavendra:
**Coarse Differentiation and Multi-flows in Planar Graphs.**

- Paul Beame, Dang-Trinh Huynh-Ngoc:
**Multiparty Communication Complexity of AC^0.**

- Manindra Agrawal, V. Vinay:
**Arithmetic Circuits: A Chasm at Depth Four.**

- Moritz Müller:
**Valiant-Vazirani Lemmata for Various Logics.**

- Or Meir:
**On the Efficiency of Non-Uniform PCPP Verifiers.**

- Noga Alon, Rina Panigrahy, Sergey Yekhanin:
**Deterministic Approximation Algorithms for the Nearest Codeword Problem.**

- Noga Alon, Shai Gutner:
**Kernels for the Dominating Set Problem on Graphs with an Excluded Minor.**

- Scott Aaronson:
**On Perfect Completeness for QMA.**

- Lior Malka:
**Instance-Dependent Commitment Schemes and the Round Complexity of Perfect Zero-Knowledge Proofs.**

- Klim Efremenko:
**3-Query Locally Decodable Codes of Subexponential Length.**

- (duplicate entry was deleted)
- Dana Moshkovitz, Ran Raz:
**Two Query PCP with Sub-Constant Error.**

- Shachar Lovett, Tali Kaufman:
**Worst case to Average case reductions for polynomials.**

- Dmitry Itsykson:
**Structural complexity of AvgBPP.**

- Neeraj Kayal, Timur Nezhmetdinov:
**Factoring groups efficiently.**

- Olaf Beyersdorff, Johannes Köbler, Sebastian Müller:
**Nondeterministic Instance Complexity and Proof Systems with Advice.**

- Ryan Williams:
**Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas.**

- Felix Brandt, Felix A. Fischer, Markus Holzer:
**On Iterated Dominance, Matrix Elimination, and Matched Paths.**

- Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer:
**Universal Quantum Circuits.**

- Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
**Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized.**

- Ido Ben-Eliezer, Rani Hod, Shachar Lovett:
**Random low degree polynomials are hard to approximate.**

- Alexander A. Razborov:
**A simple proof of Bazzi's theorem.**

- Paul Beame, Dang-Trinh Huynh-Ngoc:
**Multiparty Communication Complexity and Threshold Circuit Size of AC^0.**

- Yijia Chen, Jörg Flum:
**A logic for PTIME and a parameterized halting problem.**

- Sanjeeb Dash:
**On the complexity of cutting plane proofs using split cuts.**

- Farid M. Ablayev, Airat Khasianov, Alexander Vasiliev:
**On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions.**

- Vikraman Arvind, Partha Mukhopadhyay:
**Quantum Query Complexity of Multilinear Identity Testing.**

- Tomás Feder, Carlos S. Subi:
**Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised).**

- Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
**Testing Linear-Invariant Non-Linear Properties.**

- Noam Berger, Nevin Kapur, Leonard J. Schulman, Vijay V. Vazirani:
**Solvency Games.**

- Ulrich Schöpp, Martin Hofmann:
**Pointer Programs and Undirected Reachability.**

- Vitaly Feldman:
**On The Power of Membership Queries in Agnostic Learning.**

- Scott Aaronson, John Watrous:
**Closed Timelike Curves Make Quantum and Classical Computing Equivalent.**

- Cristopher Moore, Alexander Russell:
**A simple constant-probability RP reduction from NP to Parity P.**

- Piotr Berman, Marek Karpinski, Alexander Zelikovsky:
**1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two.**

- Brendan Juba, Madhu Sudan:
**Universal Semantic Communication II: A Theory of Goal-Oriented Communication.**

- Andrew Drucker:
**Multitask Efficiencies in the Decision Tree Model.**

- Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
**Hierarchy Theorems for Property Testing.**

- Victor Chen:
**A Hypergraph Dictatorship Test with Perfect Completeness.**

- Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena:
**Trading GRH for algebra: algorithms for factoring polynomials and related structures.**

- Chris Peikert:
**Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem.**

- Marek Karpinski, Warren Schudy:
**Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems.**

- Adi Akavia:
**Finding Significant Fourier Transform Coefficients Deterministically and Locally.**

- Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
**Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.**

- Madhur Tulsiani:
**CSP Gaps and Reductions in the Lasserre Hierarchy.**

- Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra:
**List Decoding Tensor Products and Interleaved Codes.**

- Jack H. Lutz:
**A Divergence Formula for Randomness and Dimension.**

- Zenon Sadowski:
**Optimal Proof Systems and Complete Languages.**

- Nitin Saxena, C. Seshadhri:
**An Almost Optimal Rank Bound for Depth-3 Identities.**

- Marc Kaplan, Sophie Laplante:
**Kolmogorov complexity and combinatorial methods in communication complexity.**

- Chris Calabro:
**A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths.**

- Shachar Lovett, Tali Kaufman:
**The List-Decoding Size of Reed-Muller Codes.**