Electron. Colloquium Comput. Complex.

Publications

2024

Pavel Hrubes
A subquadratic upper bound on sum-of-squares compostion formulas. Electron. Colloquium Comput. Complex. (2024)
Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz
The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices. Electron. Colloquium Comput. Complex. (2024)
Yaroslav Alekseev, Yuval Filmus, Alexander Smal
Lifting dichotomies. Electron. Colloquium Comput. Complex. (2024)
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere
Black-Box PPP is not Turing-Closed. Electron. Colloquium Comput. Complex. (2024)
Dmytro Gavinsky
Unambiguous parity-query complexity. Electron. Colloquium Comput. Complex. (2024)
Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann
Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree. Electron. Colloquium Comput. Complex. (2024)
Mitali Bafna, Noam Lifshitz, Dor Minzer
Constant Degree Direct Product Testers with Small Soundness. Electron. Colloquium Comput. Complex. (2024)
Tal Yankovitz
A stronger bound for linear 3-LCC. Electron. Colloquium Comput. Complex. (2024)
Dor Minzer, Kai Zhe Zheng
Near Optimal Alphabet-Soundness Tradeoff PCPs. Electron. Colloquium Comput. Complex. (2024)
Omkar Baraskar, Agrim Dewan, Chandan Saha
Testing equivalence to design polynomials. Electron. Colloquium Comput. Complex. (2024)
Omri Shmueli
Quantum Algorithms in a Superposition of Spacetimes. Electron. Colloquium Comput. Complex. (2024)
Changrui Mu, Shafik Nassar, Ron Rothblum, Prashant Nalini Vasudevan
Strong Batching for Non-Interactive Statistical Zero-Knowledge. Electron. Colloquium Comput. Complex. (2024)
Xinyu Mao, Guangxu Yang, Jiapeng Zhang
Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing. Electron. Colloquium Comput. Complex. (2024)
Oded Goldreich
On locally-characterized expander graphs (a survey). Electron. Colloquium Comput. Complex. (2024)
Ashish Dwivedi, Zeyu Guo, Ben Lee Volk
Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields. Electron. Colloquium Comput. Complex. (2024)
Elette Boyle, Ilan Komargodski, Neekon Vafa
Memory Checking Requires Logarithmic Overhead. Electron. Colloquium Comput. Complex. (2024)
Prasad Chaugule, Nutan Limaye
On the closures of monotone algebraic classes and variants of the determinant. Electron. Colloquium Comput. Complex. (2024)
Pavel Hrubes
Hard submatrices for non-negative rank and communication complexity }. Electron. Colloquium Comput. Complex. (2024)
Mason DiCicco, Vladimir Podolskii, Daniel Reichman
Nearest Neighbor Complexity and Boolean Circuits. Electron. Colloquium Comput. Complex. (2024)
Kuan Cheng, Ruiyang Wu
Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors. Electron. Colloquium Comput. Complex. (2024)
Noam Mazor, Rafael Pass
Search-to-Decision Reductions for Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2024)
Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak
Exponential Separation Between Powers of Regular and General Resolution Over Parities. Electron. Colloquium Comput. Complex. (2024)
Paul Beame, Niels Kornerup
Quantum Time-Space Tradeoffs for Matrix Problems. Electron. Colloquium Comput. Complex. (2024)
Yotam Dikstein, Irit Dinur, Alexander Lubotzky
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs. Electron. Colloquium Comput. Complex. (2024)
Sreejata Kishor Bhattacharya
Aaronson-Ambainis Conjecture Is True For Random Restrictions. Electron. Colloquium Comput. Complex. (2024)
Noga Amit, Orr Paradise, Guy N. Rothblum, Shafi Goldwasser
Models That Prove Their Own Correctness. Electron. Colloquium Comput. Complex. (2024)
Takashi Ishizuka
PLS is contained in PLC. Electron. Colloquium Comput. Complex. (2024)
Yanyi Liu, Rafael Pass
A Direct PRF Construction from Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2024)
Yanyi Liu, Noam Mazor, Rafael Pass
A Note on Zero-Knowledge for NP and One-Way Functions. Electron. Colloquium Comput. Complex. (2024)
Kuan Cheng, Yichuan Wang
$BPL\subseteq L-AC^1$. Electron. Colloquium Comput. Complex. (2024)
Harpreet Bedi
Degree 2 lower bound for Permanent in arbitrary characteristic. Electron. Colloquium Comput. Complex. (2024)
Shuichi Hirahara, Naoto Ohsaka
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. Electron. Colloquium Comput. Complex. (2024)
Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann
Proof Complexity of Propositional Model Counting. Electron. Colloquium Comput. Complex. (2024)
Siu On Chan, Hiu Tsun Ng, Sijin Peng
How Random CSPs Fool Hierarchies. Electron. Colloquium Comput. Complex. (2024)
Sam Buss, Emre Yolcu
Regular resolution effectively simulates resolution. Electron. Colloquium Comput. Complex. (2024)
Noel Arteche, Gaia Carenini, Matthew Gray
Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard. Electron. Colloquium Comput. Complex. (2024)
Daniel Kane, Anthony Ostuni, Kewen Wu
Locality Bounds for Sampling Hamming Slices. Electron. Colloquium Comput. Complex. (2024)
Sabee Grewal, Justin Yirka
The Entangled Quantum Polynomial Hierarchy Collapses. Electron. Colloquium Comput. Complex. (2024)
Hamed Hatami, Pooya Hatami
Structure in Communication Complexity and Constant-Cost Complexity Classes. Electron. Colloquium Comput. Complex. (2024)
Joshua Cook, Dana Moshkovitz
Explicit Time and Space Efficient Encoders Exist Only With Random Access. Electron. Colloquium Comput. Complex. (2024)
Karthik C. S., Pasin Manurangsi
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results. Electron. Colloquium Comput. Complex. (2024)
Dean Doron, Jonathan Mosheiff, Mary Wootters
When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? Electron. Colloquium Comput. Complex. (2024)
Shuichi Hirahara, Naoto Ohsaka
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration. Electron. Colloquium Comput. Complex. (2024)
Bruno Loff, Alexey Milovanov
The hardness of decision tree complexity. Electron. Colloquium Comput. Complex. (2024)
Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria
Redundancy for MaxSAT. Electron. Colloquium Comput. Complex. (2024)
Omar Alrabiah, Venkatesan Guruswami
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. Electron. Colloquium Comput. Complex. (2024)
Swagato Sanyal
Randomized query composition and product distributions. Electron. Colloquium Comput. Complex. (2024)
Daniel Noble, Brett Hemenway, Rafail Ostrovsky
MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier. Electron. Colloquium Comput. Complex. (2024)
Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun
On Pigeonhole Principles and Ramsey in TFNP. Electron. Colloquium Comput. Complex. (2024)
Sam Buss, Neil Thapen
A Simple Supercritical Tradeoff between Size and Height in Resolution. Electron. Colloquium Comput. Complex. (2024)