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.