Articles under category:
Circuit Complexity
Circuit Complexity
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 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 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 22 (pp 1-22)
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
by Alexander Golovnev and Ishay Haviv
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
by Alexander Golovnev and Ishay Haviv
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 15 (pp 1-33)
[CCC20 Spec Issue]
Multiparty Karchmer-Wigderson Games and Threshold Circuits
by Alexander Kozachinskiy and Vladimir Podolskii
Multiparty Karchmer-Wigderson Games and Threshold Circuits
by Alexander Kozachinskiy and Vladimir Podolskii
Vol 18, Article 8 (pp 1-18)
[CCC18 Spec Issue]
The Cayley Semigroup Membership Problem
by Lukas Fleischer
The Cayley Semigroup Membership Problem
by Lukas Fleischer
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 17, Article 11 (pp 1-38)
[CCC19 Spec Issue]
Hardness Magnification Near State-of-the-Art Lower Bounds
by Igor C. Oliveira, Ján Pich, and Rahul Santhanam
Hardness Magnification Near State-of-the-Art Lower Bounds
by Igor C. Oliveira, Ján Pich, and Rahul Santhanam
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 15, Article 18 (pp 1-9)
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds
by Emanuele Viola
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds
by 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 15, Article 8 (pp 1-7)
[NOTE]
Matrix Rigidity and the Croot-Lev-Pach Lemma
by Zeev Dvir and Benjamin L. Edelman
Matrix Rigidity and the Croot-Lev-Pach Lemma
by Zeev Dvir and Benjamin L. Edelman
Vol 14, Article 12 (pp 1-24)
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression
by Swastik Kopparty and Srikanth Srinivasan
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression
by Swastik Kopparty and Srikanth Srinivasan
Vol 14, Article 9 (pp 1-55)
[CCC16 Spec Issue]
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
by Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
by Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan
Vol 13, Article 9 (pp 1-34)
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
by Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
by Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan
Vol 12, Article 12 (pp 1-38)
Lower Bounds for Non-Commutative Skew Circuits
by Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan
Lower Bounds for Non-Commutative Skew Circuits
by Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan
Vol 11, Article 19 (pp 471-489)
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
by Joshua Brody and Kasper Green Larsen
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
by Joshua Brody and Kasper Green Larsen
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
Vol 10, Article 12 (pp 297-339)
Width-Parametrized SAT: Time--Space Tradeoffs
by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang
Width-Parametrized SAT: Time--Space Tradeoffs
by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang
Vol 10, Article 8 (pp 199-215)
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
by Eric Allender and Klaus-Jörn Lange
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
by Eric Allender and Klaus-Jörn Lange
Vol 10, Article 5 (pp 107-131)
Competing-Provers Protocols for Circuit Evaluation
by Gillat Kol and Ran Raz
Competing-Provers Protocols for Circuit Evaluation
by Gillat Kol and Ran Raz
Vol 8, Article 10 (pp 231-238)
[NOTE]
Monotone Circuits: One-Way Functions versus Pseudorandom Generators
by Oded Goldreich and Rani Izsak
Monotone Circuits: One-Way Functions versus Pseudorandom Generators
by Oded Goldreich and Rani Izsak
Vol 7, Article 13 (pp 185-188)
[NOTE]
Computing Polynomials with Few Multiplications
by Shachar Lovett
Computing Polynomials with Few Multiplications
by Shachar Lovett
Vol 7, Article 12 (pp 177-184)
[NOTE]
On Circuit Lower Bounds from Derandomization
by Scott Aaronson and Dieter van Melkebeek
On Circuit Lower Bounds from Derandomization
by Scott Aaronson and Dieter van Melkebeek