complexity
an archive of posts with this tag
| Nov 07, 2025 | Borders, Debordering, and Algebraic Complexity |
|---|---|
| Feb 07, 2025 | Oblivious Classes Revisited: Lower Bounds and Hierarchies |
| Oct 24, 2024 | Communication Complexity of Partial XOR Functions |
| Apr 17, 2023 | Criticality of AC0-formulae |
| Mar 03, 2023 | Approximating CSPs in the streaming setting |
| Feb 10, 2023 | Collaborative Top Distribution Identifications with Limited Interaction |
| Nov 18, 2022 | Derandomization from Time-Space Tradeoffs |
| Nov 11, 2022 | The Composition Complexity of Majority |
| Sep 23, 2022 | A better-than-3 log n depth lower bound for De Morgan formulas with restrictions on top gates |
| Apr 08, 2022 | Are quantum speedups for learning expressive classes possible? |
| Nov 19, 2021 | Algorithms and Barriers for Fast Matrix Multiplication |
| Nov 05, 2021 | Demystifying the border of depth-3 algebraic circuits |
| Oct 29, 2021 | Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits |