Articles under category:
Circuit Complexity
Circuit Complexity
|
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 |