CCC A

38 papers

YearTitle / Authors
202439th Computational Complexity Conference, CCC 2024, Ann Arbor, MI, USA, July 22-25, 2024
Rahul Santhanam
2024A Strong Direct Sum Theorem for Distributional Query Complexity.
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
2024A Subquadratic Upper Bound on Sum-Of-Squares Composition Formulas.
Pavel Hrubes
2024A Technique for Hardness Amplification Against AC⁰.
William M. Hoza
2024Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries.
Gil Cohen, Tal Yankovitz
2024BPL ⊆ L-AC¹.
Kuan Cheng, Yichuan Wang
2024Baby PIH: Parameterized Inapproximability of Min CSP.
Venkatesan Guruswami, Xuandi Ren, Sai Sandeep
2024Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture.
Peter Bürgisser, Mahmut Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson
2024Depth-d Frege Systems Are Not Automatable Unless P = NP.
Theodoros Papamakarios
2024Derandomizing Logspace with a Small Shared Hard Drive.
Edward Pyne
2024Dimension Independent Disentanglers from Unentanglement and Applications.
Fernando Granha Jeronimo, Pei Wu
2024Distribution-Free Proofs of Proximity.
Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron D. Rothblum
2024Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity.
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2024Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs.
Xin Li, Yan Zhong
2024Explicit Time and Space Efficient Encoders Exist Only with Random Access.
Joshua Cook, Dana Moshkovitz
2024Exponential Separation Between Powers of Regular and General Resolution over Parities.
Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorák
2024Failure of Feasible Disjunction Property for k-DNF Resolution and NP-Hardness of Automating It.
Michal Garlík
2024Finding Missing Items Requires Strong Forms of Randomness.
Amit Chakrabarti, Manuel Stoeckl
2024Finer-Grained Hardness of Kernel Density Estimation.
Josh Alman, Yunfeng Guan
2024Front Matter, Table of Contents, Preface, Conference Organization.
2024Gap MCSP Is Not (Levin) NP-Complete in Obfustopia.
Noam Mazor, Rafael Pass
2024Hard Submatrices for Non-Negative Rank and Communication Complexity.
Pavel Hrubes
2024Information Dissemination via Broadcasts in the Presence of Adversarial Noise.
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh R. Saxena
2024Lifting Dichotomies.
Yaroslav Alekseev, Yuval Filmus, Alexander Smal
2024Linear-Size Boolean Circuits for Multiselection.
Justin Holmgren, Ron Rothblum
2024Local Enumeration and Majority Lower Bounds.
Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Navid Talebanfard
2024Low-Depth Algebraic Circuit Lower Bounds over Any Field.
Michael A. Forbes
2024Lower Bounds for Set-Multilinear Branching Programs.
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
2024On the Degree of Polynomials Computing Square Roots Mod p.
Kiran S. Kedlaya, Swastik Kopparty
2024Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
2024Pseudorandomness, Symmetry, Smoothing: I.
Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola
2024Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure.
Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou
2024Quantum Automating TC⁰-Frege Is LWE-Hard.
Noel Arteche, Gaia Carenini, Matthew Gray
2024Search-To-Decision Reductions for Kolmogorov Complexity.
Noam Mazor, Rafael Pass
2024Solving Unique Games over Globally Hypercontractive Graphs.
Mitali Bafna, Dor Minzer
2024Streaming Zero-Knowledge Proofs.
Graham Cormode, Marcel Dall'Agnol, Tom Gur, Chris Hickey
2024The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise.
Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, Penghui Yao
2024The Entangled Quantum Polynomial Hierarchy Collapses.
Sabee Grewal, Justin Yirka