Articles under category:
Complexity
Complexity
Vol 20, Article 5 (pp 1-22)
On the Elementary Construction of High-Dimensional Expanders by Kaufman and Oppenheim
by Prahladh Harsha and Ramprasad Saptharishi
On the Elementary Construction of High-Dimensional Expanders by Kaufman and Oppenheim
by Prahladh Harsha and Ramprasad Saptharishi
Vol 20, Article 4 (pp 1-13)
[Boolean Spec Issue]
Influential Coalitions for Boolean Functions I: Constructions
by Jean Bourgain, Jeff Kahn, and Gil Kalai
Influential Coalitions for Boolean Functions I: Constructions
by Jean Bourgain, Jeff Kahn, and Gil Kalai
Vol 20, Article 3 (pp 1-87)
Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources
by Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, and Thomas Vidick
Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources
by Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, and Thomas Vidick
Vol 20, Article 2 (pp 1-19)
New Distinguishers for Negation-Limited Weak Pseudorandom Functions
by Zhihuai Chen, Siyao Guo, Qian Li, Chengyu Lin, and Xiaoming Sun
New Distinguishers for Negation-Limited Weak Pseudorandom Functions
by Zhihuai Chen, Siyao Guo, Qian Li, Chengyu Lin, and Xiaoming Sun
Vol 20, Article 1 (pp 1-70)
Polynomial Identity Testing via Evaluation of Rational Functions
by Ivan Hu, Dieter van Melkebeek, and Andrew Morgan
Polynomial Identity Testing via Evaluation of Rational Functions
by Ivan Hu, Dieter van Melkebeek, and Andrew Morgan
Vol 19, Article 12 (pp 1-30)
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse
Vol 19, Article 11 (pp 1-14)
A Strong XOR Lemma for Randomized Query Complexity
by Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu
A Strong XOR Lemma for Randomized Query Complexity
by Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu
Vol 19, Article 10 (pp 1-44)
Separating $k$-Player from $t$-Player One-Way Communication, with Applications to Data Streams
by Elbert Du, Michael Mitzenmacher, David Woodruff, and Guang Yang
Separating $k$-Player from $t$-Player One-Way Communication, with Applications to Data Streams
by Elbert Du, Michael Mitzenmacher, David Woodruff, and Guang Yang
Vol 19, Article 7 (pp 1-51)
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
by Yuval Filmus, Or Meir, and Avishay Tal
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
by Yuval Filmus, Or Meir, and Avishay Tal
Vol 18, Article 17 (pp 1-11)
[NOTE]
A Stochastic Calculus Approach to the Oracle Separation of $\mathsf{BQP}$ and $\mathsf{PH}$
by Xinyu Wu
A Stochastic Calculus Approach to the Oracle Separation of $\mathsf{BQP}$ and $\mathsf{PH}$
by Xinyu Wu
Vol 18, Article 13 (pp 1-65)
[RANDOM18 Spec Issue]
Round Complexity Versus Randomness Complexity in Interactive Proofs
by Maya Leshkowitz
Round Complexity Versus Randomness Complexity in Interactive Proofs
by Maya Leshkowitz
Vol 18, Article 12 (pp 1-25)
From Local to Robust Testing via Agreement Testing
by Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi
From Local to Robust Testing via Agreement Testing
by Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi
Vol 18, Article 10 (pp 1-12)
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines
by Emanuele Viola
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines
by Emanuele Viola
Vol 18, Article 4 (pp 1-46)
[APRX-RND19 Spec Issue]
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas
by Rocco A. Servedio and Li-Yang Tan
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas
by Rocco A. Servedio and Li-Yang Tan
Vol 18, Article 3 (pp 1-29)
[APRX-RND16 Spec Issue]
Near-Optimal NP-Hardness of Approximating Max $k$-CSP$_R$
by Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan
Near-Optimal NP-Hardness of Approximating Max $k$-CSP$_R$
by Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan
Vol 18, Article 2 (pp 1-18)
[RANDOM18 Spec Issue]
Sunflowers and Robust Sunflowers from Randomness Extractors
by Xin Li, Shachar Lovett, and Jiapeng Zhang
Sunflowers and Robust Sunflowers from Randomness Extractors
by Xin Li, Shachar Lovett, and Jiapeng Zhang
Vol 17, Article 7 (pp 1-46)
[APRX-RND19 Spec Issue]
The Large-Error Approximate Degree of AC$^0$
by Mark Bun and Justin Thaler
The Large-Error Approximate Degree of AC$^0$
by Mark Bun and Justin Thaler
Vol 17, Article 4 (pp 1-35)
[APRX-RND19 Spec Issue]
Deterministic Approximation of Random Walks in Small Space
by Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan
Deterministic Approximation of Random Walks in Small Space
by Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan
Vol 16, Article 13 (pp 1-30)
Monotone Circuit Lower Bounds from Resolution
by Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov
Monotone Circuit Lower Bounds from Resolution
by Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov
Vol 16, Article 7 (pp 1-50)
More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials
by Chin Ho Lee and Emanuele Viola
More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials
by Chin Ho Lee and Emanuele Viola
Vol 15, Article 17 (pp 1-20)
Separation of AC$^0[\oplus]$ Formulas and Circuits
by Ben Rossman and Srikanth Srinivasan
Separation of AC$^0[\oplus]$ Formulas and Circuits
by Ben Rossman and Srikanth Srinivasan
Vol 14, Article 5 (pp 1-27)
Randomized Query Complexity of Sabotaged and Composed Functions
by Shalev Ben-David and Robin Kothari
Randomized Query Complexity of Sabotaged and Composed Functions
by Shalev Ben-David and Robin Kothari
Vol 13, Article 10 (pp 1-19)
On the Hardness of Approximating Balanced Homogenous 3-Lin
by Johan Håstad and Rajsekar Manokaran
On the Hardness of Approximating Balanced Homogenous 3-Lin
by Johan Håstad and Rajsekar Manokaran
Vol 12, Article 9 (pp 1-23)
[APRX-RND14 Spec Issue]
Communication Complexity of Set-Disjointness for All Probabilities
by Mika Göös and Thomas Watson
Communication Complexity of Set-Disjointness for All Probabilities
by Mika Göös and Thomas Watson
Vol 11, Article 14 (pp 357-393)
Non-Commutative Arithmetic Circuits with Division
by Pavel Hrubeš and Avi Wigderson
Non-Commutative Arithmetic Circuits with Division
by Pavel Hrubeš and Avi Wigderson