Volume 19, 2012
: Rank Bounds for a Hierarchy of Lovász and Schrijver.
: Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise.
: On the Effect of the Proximity Parameter on Property Testers.
, Emanuele Viola
: On the complexity of constructing pseudorandom functions (especially when they don't exist).
: Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction.
: An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem.
: Clique Problem, Cutting Plane Proofs, and Communication Complexity.
: Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity.
: Limitations of Incremental Dynamic Programs.
, Noga Zewi
: A new upper bound on the query complexity for testing generalized Reed-Muller codes.
, Madhu Sudan
: Some closure features of locally testable affine-invariant properties.
: A Singly-Exponential Time Algorithm for Computing Nonnegative Rank.
: Parallel Complexity for Matroid Intersection and Matroid Parity Problems.
: An exponential lower bound for the sum of powers of bounded degree polynomials.
: Pseudorandomness for Permutation Branching Programs Without the Group Theory.
: Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds.
: A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata.
: An improved lower bound for the randomized decision tree complexity of recursive majority.
Siu On Chan
: Approximation Resistance from Pairwise Independent Subgroups.
: New Limits to Classical and Quantum Instance Compression.
: Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption.
Michael A. Forbes
, Amir Shpilka
: Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs.
: A Derandomized Switching Lemma and an Improved Derandomization of AC0.
, Nicola Galesi
: Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems.
: Proof vs. Truth in Computational Complexity.
: A note on the real $\tau$-conjecture and the distribution of roots.
: A rank lower bound for cutting planes proofs of Ramsey Theorem.
: On the correlation of parity and small-depth circuits.
: How to Construct Quantum Random Functions.
: Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four.
: New Independent Source Extractors with Exponential Improvement.
: Properties and Applications of Boolean Function Composition.
: Strong LTCs with inverse polylogarithmic rate and soundness.