- Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak:
Exponential Separation Between Powers of Regular and General Resolution Over Parities. Electron. Colloquium Comput. Complex. TR24: TR24-022 (2024) - Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich:
Launching Identity Testing into (Bounded) Space. Electron. Colloquium Comput. Complex. TR24: TR24-041 (2024) - Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria:
Redundancy for MaxSAT. Electron. Colloquium Comput. Complex. TR24: TR24-045 (2024) - Elette Boyle, Ilan Komargodski, Neekon Vafa:
Memory Checking Requires Logarithmic Overhead. Electron. Colloquium Comput. Complex. TR24: TR24-014 (2024) - Sam Buss, Neil Thapen:
A Simple Supercritical Tradeoff between Size and Height in Resolution. Electron. Colloquium Comput. Complex. TR24 (2024) - Sam Buss, Emre Yolcu:
Regular resolution effectively simulates resolution. Electron. Colloquium Comput. Complex. TR24: TR24-033 (2024) - Siu On Chan, Hiu Tsun Ng, Sijin Peng:
How Random CSPs Fool Hierarchies. Electron. Colloquium Comput. Complex. TR24: TR24-066 (2024) - Prasad Chaugule, Nutan Limaye:
On the closures of monotone algebraic classes and variants of the determinant. Electron. Colloquium Comput. Complex. TR24: TR24-021 (2024) - Sravanthi Chede, Leroy Chew, Anil Shukla:
Circuits, Proofs and Propositional Model Counting. Electron. Colloquium Comput. Complex. TR24: TR24-081 (2024) - Kuan Cheng, Ruiyang Wu:
Randomness Extractors in $\mathrm{AC}0$ and $\mathrm{NC}1$: Optimal up to Constant Factors. Electron. Colloquium Comput. Complex. TR24: TR24-040 (2024) - Kuan Cheng, Yichuan Wang:
$BPL\subseteq L-AC1$. Electron. Colloquium Comput. Complex. TR24: TR24-048 (2024) - Gil Cohen, Itay Cohen, Gal Maor:
Tight Bounds for the Zig-Zag Product. Electron. Colloquium Comput. Complex. TR24: TR24-089 (2024) - Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz:
A Study of Error Reduction Polynomials. Electron. Colloquium Comput. Complex. TR24: TR24-090 (2024) - Joshua Cook, Dana Moshkovitz:
Explicit Time and Space Efficient Encoders Exist Only With Random Access. Electron. Colloquium Comput. Complex. TR24: TR24-032 (2024) - Mason DiCicco, Vladimir Podolskii, Daniel Reichman:
Nearest Neighbor Complexity and Boolean Circuits. Electron. Colloquium Comput. Complex. TR24: TR24-025 (2024) - Yotam Dikstein, Irit Dinur, Alexander Lubotzky:
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs. Electron. Colloquium Comput. Complex. TR24: TR24-019 (2024) - Yotam Dikstein, Max Hopkins:
Chernoff Bounds and Reverse Hypercontractivity on HDX. Electron. Colloquium Comput. Complex. TR24: TR24-082 (2024) - Dean Doron, Jonathan Mosheiff, Mary Wootters:
When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? Electron. Colloquium Comput. Complex. TR24: TR24-091 (2024) - Ashish Dwivedi, Zeyu Guo, Ben Lee Volk:
Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields. Electron. Colloquium Comput. Complex. TR24: TR24-028 (2024) - Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami:
No Complete Problem for Constant-Cost Randomized Communication. Electron. Colloquium Comput. Complex. TR24: TR24-064 (2024) - Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere:
Black-Box PPP is not Turing-Closed. Electron. Colloquium Comput. Complex. TR24: TR24-010 (2024) - Karthik Gajulapalli, Alexander Golovnev, Samuel King:
On the Power of Adaptivity for Function Inversion. Electron. Colloquium Comput. Complex. TR24: TR24-054 (2024) - Karthik Gajulapalli, Zeyong Li, Ilya Volkovich:
Oblivious Classes Revisited: Lower Bounds and Hierarchies. Electron. Colloquium Comput. Complex. TR24: TR24-049 (2024) - Dmytro Gavinsky:
Unambiguous parity-query complexity. Electron. Colloquium Comput. Complex. TR24: TR24-009 (2024) - Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan:
Hilbert Functions and Low-Degree Randomness Extractors. Electron. Colloquium Comput. Complex. TR24: TR24-092 (2024) - Sabee Grewal, Justin Yirka:
The Entangled Quantum Polynomial Hierarchy Collapses. Electron. Colloquium Comput. Complex. TR24: TR24-006 (2024) - Meghal Gupta, Mihir Singhal, Hongxun Wu:
Optimal quantile estimation: beyond the comparison model. Electron. Colloquium Comput. Complex. TR24: TR24-065 (2024) - Rohit Gurjar, Taihei Oki, Roshan Raj:
Fractional Linear Matroid Matching is in quasi-NC. Electron. Colloquium Comput. Complex. TR24: TR24-044 (2024) - Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. Electron. Colloquium Comput. Complex. TR24: TR24-075 (2024) - Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret:
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers. Electron. Colloquium Comput. Complex. TR24: TR24-079 (2024)