CCC'25 Program
Schedule The slots for contributed talks are 30
minutes (including 5 minutes for questions and changing speakers),
and the invited talk on Wednesday has a duration of one hour. The
business meeting is on Wednesday evening. All the talks and the
business meeting will be held at the Fields
Institute.
All times below are in Eastern Daylight Time (EDT), which is
UTC-4.
Proceedings: The open-access official version via
LIPIcs is here. The talk videos, courtesy the Fields Institute, are also linked in the program.
Tuesday, August 5
| 9:30 |
Registration and coffee |
| 10:25 |
Opening remarks |
| 10:30 |
Direct Sum for Parity Decision
Trees (paper, talk)
Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre,
Weiqiang Yuan
|
| 11:00 |
Super-critical Trade-offs in
Resolution over Parities Via Lifting (paper, talk)
Arkadev Chattopadhyay, Pavel Dvořák
|
| 11:30 |
Amortized Closure and Its
Applications in Lifting for Resolution over Parities (paper, talk)
Klim Efremenko, Dmitry Itsykson
|
| 12:00 |
Lunch |
| 14:00 |
Biased Linearity Testing in the
1% Regime (paper, talk)
Subhash Khot, Kunal Mittal
|
| 14:30 |
A Min-Entropy Approach to
Multi-Party Communication Lower Bounds (paper, talk)
Mi-Ying Huang, Xinyu Mao, Shuo Wang, Guangxu Yang,
Jiapeng Zhang
|
| 15:00 |
Coffee break |
| 15:30 |
Generalised Linial-Nisan
Conjecture is False for DNFs (paper, talk)
Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert
Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan
|
| 16:00 |
Hardness of clique approximation
for monotone circuits (paper, talk)
Jarosław Błasiok, Linus Meierhöfer
|
| 16:30 |
Lifting with Colourful
Sunflowers (paper, talk)
Susanna de Rezende, Marc Vinyals
|
Wednesday, August 6
| 9:00 |
Invited talk by Ian Mertz
How to Reuse Space (talk)
Abstract: We study the question of whether used memory can be
an asset to space-bounded computation. We will survey this
active line of work, from its major successes in complexity
theory to the current state of the catalytic computing model,
with a focus on techniques and future directions. |
| 10:00 |
Coffee break |
| 10:30 |
New Codes on High Dimensional
Expanders (paper, talk)
Rachel Yun Zhang, Siqi Liu, Irit Dinur
|
| 11:00 |
Sparser Abelian High Dimensional
Expanders (paper, talk)
Yotam Dikstein, Siqi Liu, Avi Wigderson
|
| 11:30 |
Online Condensing of
Unpredictable Sources via Random Walks (paper, talk)
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
|
| 12:00 |
Lunch |
| 14:00 |
Switching Graph Matrix Norm
Bounds: from i.i.d. to Random Regular Graphs (paper, talk)
(winner - Best student paper award)
Jeff Xu
|
| 14:30 |
Quantum Threshold is Powerful (paper, talk)
(winner - Best paper award)
Jackson Morris, Daniel Grier
|
| 15:00 |
Coffee break |
| 15:30 |
On the Automatability of
Tree-Like k-DNF Resolution (paper, talk)
Gaia Carenini, Susanna de Rezende
|
| 16:00 |
A Lower Bound for k-DNF
Resolution on Random CNF Formulas via Expansion (paper, talk)
Dmitry Sokolov, Anastasia Sofronova
|
| 16:30 |
Provably Total Functions in the
Polynomial Hierarchy (paper, talk)
Noah Fleming, Christophe Marciot, Deniz Imrek
|
| 17:00 |
Business meeting |
Thursday, August 7
| 9:00 |
From an odd arity signature to a
Holant dichotomy (paper, talk)
Boning Meng, Juqiu Wang, Mingji Xia, Jiayi Zheng
|
| 9:30 |
Counting Martingales for Measure
and Dimension in Complexity Classes (paper, talk)
John Hitchcock, Adewale Sekoni, Hadi Shafei
|
| 10:00 |
Coffee break |
| 10:30 |
Algebraic Pseudorandomness in
VNC^0 (paper, talk)
Robert Andrews
|
| 11:00 |
Reconstruction of Depth 3
Arithmetic Circuits with Top Fan-in 3 (paper, talk)
Shubhangi Saraf, Devansh Shringi
|
| 11:30 |
Algebraic metacomplexity and
representation theory (paper, talk)
Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo,
Christian Ikenmeyer, Vladimir Lysikov
|
| 12:00 |
Lunch |
| 14:00 |
Improved separation between
quantum and classical computers for sampling and
functional tasks (paper, talk)
Simon Marshall, Scott Aaronson, Vedran Dunjko
|
| 14:30 |
New Lower-bounds for Quantum
Computation with Non-Collapsing Measurements (paper, talk)
David Miloschewsky, Supartha Podder
|
| 15:00 |
Coffee break |
| 15:30 |
Multiplicative Extractors for
Samplable Distributions (paper, talk)
Ronen Shaltiel
|
| 16:00 |
How to Construct Random Strings
(paper, talk)
Oliver Korten, Rahul Santhanam
|
| 16:30 |
Towards Free Lunch
Derandomization from Necessary Assumptions (and OWFs) (paper, talk)
Marshall Ball, Lijie Chen, Roei Tell
|
Friday, August 8
| 9:00 |
Characterizing the
Distinguishability of Product Distributions through
Multicalibration (paper, talk)
Cassandra Marcussen, Aaron Putterman, Salil Vadhan
|
| 9:30 |
Witness Encryption and
NP-hardness of Learning (paper, talk)
Halley Goldberg, Valentine Kabanets
|
| 10:00 |
Coffee break |
| 10:30 |
Hardness Amplification for
Real-Valued Functions (paper, talk)
Yunqi Li, Prashant Nalini Vasudevan
|
| 11:00 |
Near-Optimal Averaging Samplers
and Matrix Samplers (paper, talk)
Zhiyang Xun, David Zuckerman
|
| 11:30 |
Pseudorandom bits for
non-commutative programs (paper, talk)
Chin Ho Lee, Emanuele Viola
|
| 12:00 |
Lunch |
| 14:00 |
Space-bounded quantum
interactive proof systems (paper, talk)
François Le Gall, Yupan Liu, Harumichi Nishimura,
Qisheng Wang
|
| 14:30 |
Directed st-connectivity with
few paths is in quantum logspace (paper, talk)
Roman Edenhofer, Simon Apers
|
| 15:00 |
Coffee break |
| 15:30 |
List Decoding Quotient
Reed-Muller Codes (paper, talk)
Omri Gotlib, Tali Kaufman, Shachar Lovett
|
| 16:00 |
Quantum LDPC Codes of Almost
Linear Distance via Iterated Homological Products (paper, talk)
Louis Golowich, Venkatesan Guruswami
|
| 16:30 |
Tight bounds for stream
decodable error-correcting codes (paper, talk)
Meghal Gupta, Venkatesan Guruswami, Mihir Singhal
|
| 17:00 |
Conclusion. |
