CCC

Publications

2024

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

volume 300, 2024

39th Computational Complexity Conference, CCC 2024, July 22-25, 2024, Ann Arbor, MI, USA CCC 300 (2024)

2023

volume 264, 2023

38th Computational Complexity Conference, CCC 2023, July 17-20, 2023, Warwick, UK CCC 264 (2023)