CCC'24 Program
Schedule The slots for contributed talks are 30 minutes (including 5 minutes for questions and changing speakers). In addition there are invited talks on Monday, Tuesday, and Wednesday which are one hour each. The conference reception and business meeting are on Monday and Tuesday evening, respectively. We are also planning a rump session (where you can discuss your favorite open problems and such) on Wednesday evening. All the talks and the business meeting will be held in the Pendleton room, located in Michigan Union. The reception will be held in Rogel Ballroom (same building). Lunch will be provided at Room 2210 (same building).
All times below are in Eastern Daylight Time (EDT).
Proceedings: The official version will be openly accessible via LIPIcs.
Monday, July 22
| 8:30 | Registration and coffee |
| 8:55 | Opening remarks |
| 9:00 |
Streaming Zero-Knowledge Proofs
Graham Cormode and Marcel Dall'Agnol and Tom Gur and Chris Hickey |
| 9:30 |
Distribution-free Proofs of Proximity
Hugo Aaronson and Tom Gur and Ninad Rajgopal and Ron Rothblum |
| 10:00 |
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal and Sagnik Mukhopadhyay |
| 10:30 | Coffee break |
| 11:00 |
Lifting Dichotomies
Yaroslav Alekseev and Yuval Filmus and Alexander Smal |
| 11:30 |
A Strong Direct Sum Theorem for Distributional Query Complexity
Guy Blanc and Caleb Koch and Carmen Strassle and Li-Yang Tan |
| 12:00 |
Finding missing items requires strong Forms of randomness
Amit Chakrabarti and Manuel Stoeckl |
| 12:30 | Lunch |
| 14:00 | Invited talk by Toni Pitassi |
| 15:00 | Coffee break |
| 15:30 |
Depth-d Frege Systems are not Automatable unless P=NP
Theodoros Papamakarios |
| 16:00 |
Failure of Feasible Disjunction Property for k-DNF Resolution and NP-Hardness of Automating It
Michal Garlik |
| 16:30 |
Quantum Automating TC^0-Frege is LWE-Hard
Noel Arteche and Gaia Carenini and Matthew Gray |
| 17:00 |
Exponential Separation between Powers of General and Regular Resolution over Parities
Sreejata Bhattacharya and Arkadev Chattopadhyay and Pavel Dvorak |
| 18:00 | Conference reception |
Tuesday, July 23
| 8:30 | Coffee |
| 9:00 |
Linear-Size Boolean Circuits for Multiselection
Justin Holmgren and Ron Rothblum |
| 9:30 |
Local Enumeration and Majority Lower Bounds
Mohit Gurumukhani and Ramamohan Paturi and Pavel Pudlak and Michael Saks and Navid Talebanfard |
| 10:00 |
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
Xin Li and Yan Zhong |
| 10:30 | Coffee break |
| 11:00 |
A Technique for Hardness Amplification against AC^0
William Hoza |
| 11:30 |
Derandomizing Logspace with a Small Shared Hard Drive
(winner - Best student paper award) Edward Pyne |
| 12:00 |
\mathsf{BPL} \subseteq \textsf{L-AC}^1
Kuan Cheng and Yichuan Wang |
| 12:30 | Lunch |
| 14:00 | Invited talk by Nutan Limaye |
| 15:00 | Coffee break |
| 15:30 |
Low-depth algebraic circuit lower bounds over any field
(winner - Best paper award) Michael A. Forbes |
| 16:00 |
Lower bounds for set-multilinear branching programs
Prerona Chatterjee and Deepanshu Kush and Shubhangi Saraf and Amir Shpilka |
| 16:30 |
A subquadratic upper bound on sum-of-squares composition formulas
Pavel Hrubes |
| 17:00 |
Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture
Mahmut Levent Dogan and Peter Burgisser and Visu Makam and Michael Walter and Avi Wigderson |
| 18:00 | Business meeting |
Wednesday, July 24
| 8:30 | Coffee |
| 9:00 |
Hard submatrices for non-negative rank and communication complexity
Pavel Hrubes |
| 9:30 |
On the degree of polynomials computing square roots mod p
Kiran Kedlaya and Swastik Kopparty |
| 10:00 |
Pseudorandomness, symmetry, smoothing: I
Harm Derksen and Peter Ivanov and Chin Ho Lee and Emanuele Viola |
| 10:30 | Coffee break |
| 11:00 |
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity
Shuichi Hirahara and Valentine Kabanets and Zhenjian Lu and Igor Oliveira |
| 11:30 |
Search-to-Decision Reductions for Kolmogorov Complexity
Naom Mazor and Rafael Pass |
| 12:00 |
Gap MCSP is not (Levin) NP-Complete in Obfustopia
Noam Mazor and Rafael Pass |
| 12:30 | Lunch |
| 14:00 | Invited talk by Adam Bouland |
| 15:00 | Coffee break |
| 15:30 |
The Computational Advantage of MIP* Vanishes in the Presence of Noise
Yangjing Dong and Honghao Fu and Anand Natarajan and Minglong Qin and Haochen Xu and Penhui Yao |
| 16:00 |
The Entangled Polynomial Hierarchy Collapses
Sabee Grewal and Justin Yirka |
| 16:30 |
Public-key pseudoentanglement and the hardness of learning ground-state entanglement structure
Adam Bouland and Bill Fefferman and Soumik Ghosh and Tony Metger and Umesh Vazirani and Chenyi Zhang and Zixin Zhou |
| 17:00 |
Dimension Independent Disentanglers from Unentanglement and Applications
Fernando Jeronimo and Pei Wu |
| 18:00 | Rump session |
Thursday, July 25
| 8:30 | Coffee |
| 9:00 |
Solving Unique Games over Globally Hypercontractive Graphs
Mitali Bafna and Dor Minzer |
| 9:30 |
Finer-Grained Hardness of Kernel Density Estimation
Josh Alman and Yungeng Guan |
| 10:00 |
Baby PIH: Parameterized Inapproximability of Min CSP
Venkatesan Guruswami and Xuandi Ren and Sai Sandeep |
| 10:30 | Coffee break |
| 11:00 |
Explicit Time and Space Efficient Encoders Exist Only with Random Access
Joshua Cook and Dana Moshkovitz |
| 11:30 |
Asymptotically-good RLCCs with $\log(n)^{2+o(1)}$ Queries
Gil Cohen and Tal Yankovitz |
| 12:00 |
Information Dissemination via Broadcasts in the Presence of Adversarial Noise
Klim Efremenko and Gillat Kol and Dmitry Paramonov and Ran Raz and Raghuvansh Saxena |
| 12:30 | Conclusion. |