On the Ring Isomorphism and Automorphism Problems
Abstract Algebra
Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy
Abstract Algebra
The Complexity of the Inertia and Some Closure Properties of GapL
Linear Algebra
Better Time-Space Lower Bounds for SAT and Related Problems
Diagonization and Simulation
Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
Probability
Monotone Circuits for Weighted Threshold Functions
Dynamic Programming
The Quantum Adversary Method and Classical Formula Size Lower Bounds
Linear Algebra
More on Noncommutative Polynomial Identity Testing
Abstract Algebra
New Results on the Complexity of the Middle Bit of Multiplication
Number Theory
On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas
Number Theory
Short PCPs Verifiable in Polylogarithmic Time
Linear Algebra
Tolerant Versus Intolerant Testing for Boolean Properties
Combinatorics
Steps toward a Mathematical Scientific Theory of Consciousness
Philosophy
On the Hardness of Approximating Multicut and Sparsest-Cut
Probability
Hardness of Max SAT with No Mixed Clauses
Combinatorics
On the Sensitivity of Cyclically-Invariant Boolean Functions
Abstract Algebra
On the Complexity of Hardness Amplification
Probability
On Constructing Parallel Pseudorandom Generators from One-Way Functions
Combinatorics
Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates
Combinatorics
Pseudorandomness for Approximate Counting and Sampling
Probability
NP with Small Advice
Diagonalization and Simulation
Average-Case Computations - Comparing AvgP, HP, and Nearly-P
Probability
If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances
Probability
Computationally Private Randomizing Polynomials and Their Applications
Probability
A Geometric Approach to Information-Theoretic Private Information Retrieval
Calculus
Prior Entanglement, Message Compression and Privacy in Quantum Communication
Probability
Topology Inside NC1
Combinatorics
Toward a Model for Backtracking and Dynamic Programming
Combinatorics
On the Complexity of Succinct Zero-Sum Games
Linear Algebra
Upper Bounds for Quantum Interactive Proofs with Competing Provers
Linear Algebra
On the Hardness of Distinguishing Mixed-State Quantum Computations
Linear Algebra