| How to Verify a Quantum Computation |
6 |
| Quantum-Walk Speedup of Backtracking Algorithms |
4 |
| On the Hardness of Learning With Errors with Binary Secrets |
2 |
| On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree |
2 |
| Randomized Polynomial-Time Identity Testing for Noncommutative Circuits |
2 |
| Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits |
2 |
| New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates |
1 |
| Closure Results for Polynomial Factorization |
1 |
| Randomized Query Complexity of Sabotaged and Composed Functions |
1 |
| Trading Information Complexity for Error |
1 |
| Certifying Polynomials for AC(0)[circle plus] Circuits, with Applications to Lower Bounds and Circuit Compression |
1 |
| Linear-Time Algorithm for Quantum 2SAT |
1 |
| Matrix Rigidity and the Croot-Lev-Pach Lemma |
1 |
| Subsets of Cayley Graphs That Induce Many Edges |
0 |
| Fourier Sparsity and Dimension |
0 |
| A Deterministic PTAS for the Commutative Rank of Matrix Spaces |
0 |
| The Threshold for Subgroup Profiles to Agree is Logarithmic |
0 |
| Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds |
0 |
| Separation of Unbounded-Error Models in Multi-Party Communication Complexity |
0 |
| On Multiparty Communication with Large versus Unbounded Error |
0 |
| Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field |
0 |
| Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits |
0 |
| Separation of AC(0)[circle plus] Formulas and Circuits |
0 |
| Simplified Separation of Information and Communication |
0 |
| Noise Stability is Computable and Approximately Low-Dimensional |
0 |
| Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits |
0 |
| Explicit Rateless Codes for Memoryless Binary-Input Output-Symmetric Channels |
0 |
| Quantum Homomorphic Encryption for Polynomial-Size Circuits |
0 |
| Time Bounds for Streaming Problems |
0 |
| A Chasm Between Identity and Equivalence Testing with Conditional Queries |
0 |
| Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem |
0 |
| Explicit Polynomial Sequences with Maximal Spaces of Partial Derivatives and a Question of K. Mulmuley |
0 |
| Potential-Function Proofs for Gradient Methods |
0 |
| Classical Verification of Quantum Proofs |
0 |
| The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues |
0 |
| Testing k-Monotonicity The Rise and Fall of Boolean Functions |
0 |
| From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems |
0 |
| Outlaw Distributions and Locally Decodable Codes |
0 |
| Pseudorandom Generators from Polarizing Random Walks |
0 |
| The Complexity of Computing the Optimal Composition of Differential Privacy |
0 |
