default search action
39th CCC 2024: Ann Arbor, MI, USA
- Rahul Santhanam
:
39th Computational Complexity Conference, CCC 2024, July 22-25, 2024, Ann Arbor, MI, USA. LIPIcs 300, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024, ISBN 978-3-95977-331-7 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xiv
- William M. Hoza:
A Technique for Hardness Amplification Against AC⁰. 1:1-1:20 - Graham Cormode
Streaming Zero-Knowledge Proofs. 2:1-2:66 - Mitali Bafna, Dor Minzer:
Solving Unique Games over Globally Hypercontractive Graphs. 3:1-3:15 - Edward Pyne:
Derandomizing Logspace with a Small Shared Hard Drive. 4:1-4:20 - Joshua Cook, Dana Moshkovitz:
Explicit Time and Space Efficient Encoders Exist Only with Random Access. 5:1-5:54 - Sabee Grewal, Justin Yirka:
The Entangled Quantum Polynomial Hierarchy Collapses. 6:1-6:23 - Sepehr Assadi, Prantar Ghosh
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. 7:1-7:16 - Gil Cohen, Tal Yankovitz:
Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries. 8:1-8:16 - Yaroslav Alekseev, Yuval Filmus, Alexander Smal:
Lifting Dichotomies. 9:1-9:18 - Xin Li, Yan Zhong:
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs. 10:1-10:14 - Justin Holmgren, Ron Rothblum:
Linear-Size Boolean Circuits for Multiselection. 11:1-11:20 - Pavel Hrubes:
A Subquadratic Upper Bound on Sum-Of-Squares Composition Formulas. 12:1-12:11 - Pavel Hrubes:
Hard Submatrices for Non-Negative Rank and Communication Complexity. 13:1-13:12 - Peter Bürgisser, Mahmut Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson:
Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture. 14:1-14:48 - Noel Arteche, Gaia Carenini, Matthew Gray:
Quantum Automating TC⁰-Frege Is LWE-Hard. 15:1-15:25 - Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan:
A Strong Direct Sum Theorem for Distributional Query Complexity. 16:1-16:30 - Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Navid Talebanfard:
Local Enumeration and Majority Lower Bounds. 17:1-17:25 - Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola:
Pseudorandomness, Symmetry, Smoothing: I. 18:1-18:27 - Klim Efremenko
Information Dissemination via Broadcasts in the Presence of Adversarial Noise. 19:1-19:33 - Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
Lower Bounds for Set-Multilinear Branching Programs. 20:1-20:20 - Adam Bouland
Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure. 21:1-21:23 - Theodoros Papamakarios:
Depth-d Frege Systems Are Not Automatable Unless P = NP. 22:1-22:17 - Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorák:
Exponential Separation Between Powers of Regular and General Resolution over Parities. 23:1-23:32 - Hugo Aaronson, Tom Gur
Distribution-Free Proofs of Proximity. 24:1-24:18 - Kiran S. Kedlaya, Swastik Kopparty:
On the Degree of Polynomials Computing Square Roots Mod p. 25:1-25:14 - Fernando Granha Jeronimo, Pei Wu:
Dimension Independent Disentanglers from Unentanglement and Applications. 26:1-26:28 - Venkatesan Guruswami, Xuandi Ren, Sai Sandeep:
Baby PIH: Parameterized Inapproximability of Min CSP. 27:1-27:17 - Amit Chakrabarti, Manuel Stoeckl:
Finding Missing Items Requires Strong Forms of Randomness. 28:1-28:20 - Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira:
Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity. 29:1-29:56 - Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, Penghui Yao:
The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise. 30:1-30:71 - Michael A. Forbes:
Low-Depth Algebraic Circuit Lower Bounds over Any Field. 31:1-31:16 - Kuan Cheng, Yichuan Wang:
BPL ⊆ L-AC¹. 32:1-32:14 - Michal Garlík:
Failure of Feasible Disjunction Property for k-DNF Resolution and NP-Hardness of Automating It. 33:1-33:23 - Noam Mazor, Rafael Pass:
Search-To-Decision Reductions for Kolmogorov Complexity. 34:1-34:20 - Josh Alman, Yunfeng Guan:
Finer-Grained Hardness of Kernel Density Estimation. 35:1-35:21 - Noam Mazor, Rafael Pass:
Gap MCSP Is Not (Levin) NP-Complete in Obfustopia. 36:1-36:21
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-26 00:35 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: