Articles under category:
Circuit Complexity
Circuit Complexity
|
Vol 21, Article 7 (pp 1-13)
[NOTE]
Even Quantum Advice is Unlikely to Solve PP by Justin Yirka |
|
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 |
|
Vol 19, Article 12 (pp 1-30)
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 |
|
Vol 18, Article 22 (pp 1-22)
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 |
|
Vol 18, Article 15 (pp 1-33)
[CCC20 Spec Issue]
Multiparty Karchmer-Wigderson Games and Threshold Circuits by Alexander Kozachinskiy and Vladimir V. Podolskii |
|
Vol 18, Article 8 (pp 1-18)
[CCC18 Spec Issue]
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 |
|
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 |
|
Vol 16, Article 13 (pp 1-30)
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 |
|
Vol 15, Article 17 (pp 1-20)
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 |
|
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 |
|
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 |
|
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 |
|
Vol 12, Article 12 (pp 1-38)
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 |
|
Vol 11, Article 14 (pp 357-393)
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 |
|
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 |
|
Vol 10, Article 5 (pp 107-131)
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 |
|
Vol 7, Article 13 (pp 185-188)
[NOTE]
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 |
|
Vol 6, Article 7 (pp 135-177)
Elusive Functions and Lower Bounds for Arithmetic Circuits by Ran Raz |
|
Vol 1, Article 5 (pp 81-103)
Quantum Fan-out is Powerful by Peter Høyer and Robert Špalek |