Computational Complexity Conference 2025
Description
The Copmutational Complexity Conference (CCC) aims to foster research in all areas of computational complexity theory, studying the absolute and relative power of computational models under resource constraints. Typical models include deterministic, nondeterministic, randomized, and quantum models; uniform and nonuniform models; Boolean, algebraic, and continuous models. Typical resource constraints involve time, space, randomness, program size, input queries, communication, and entanglement; worst-case as well as average case. Other, more specific, topics include: probabilistic and interactive proof systems, inapproximability, proof complexity, descriptive complexity, and complexity-theoretic aspects of cryptography and machine learning. The conference also encourages results from other areas of computer science and mathematics motivated by computational complexity theory.
More info on past CCC's: https://computationalcomplexity.org/general.php .
CCC main website: https://computationalcomplexity.org/
CCC 2025 call for papers: https://computationalcomplexity.org/Archive/2025/cfp.html
Schedule
| 09:30 to 10:25 |
Registration & Coffee
|
| 10:00 to 10:30 |
Coffee Break
|
| 10:25 to 10:30 |
Opening remarks
|
| 10:30 to 11:00 |
Direct Sum for Parity Decision Trees
Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, Weiqiang Yuan |
| 11:00 to 11:30 |
Super-critical Trade-offs in Resolution over Parities Via Lifting
Arkadev Chattopadhyay, Pavel Dvořák |
| 11:30 to 12:00 |
Amortized Closure and Its Applications in Lifting for Resolution over Parities
Klim Efremenko, Dmitry Itsykson |
| 12:00 to 14:00 |
Lunch
|
| 14:00 to 14:30 |
Biased Linearity Testing in the 1% Regime
Subhash Khot, Kunal Mittal |
| 14:30 to 15:00 |
A Min-Entropy Approach to Multi-Party Communication Lower Bounds
Mi-Ying Huang, Xinyu Mao, Shuo Wang, Guangxu Yang, Jiapeng Zhang |
| 15:00 to 15:30 |
Coffee Break
|
| 15:30 to 16:00 |
Generalised Linial-Nisan Conjecture is False for DNFs
Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan |
| 16:00 to 16:30 |
Hardness of clique approximation for monotone circuits
Jarosław Błasiok, Linus Meierhöfer |
| 16:30 to 17:00 |
Lifting with Colourful Sunflowers
Susanna de Rezende, Marc Vinyals |
| 09:00 to 10:00 |
Invited talk by Ian Mertz
|
| 10:00 to 10:30 |
Coffee Break
|
| 10:30 to 11:00 |
New Codes on High Dimensional Expanders
Rachel Yun Zhang, Siqi Liu, Irit Dinur |
| 11:00 to 11:30 |
Sparser Abelian High Dimensional Expanders
Yotam Dikstein, Siqi Liu, Avi Wigderson |
| 11:30 to 12:00 |
Online Condensing of Unpredictable Sources via Random Walks
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman |
| 12:00 to 14:00 |
Lunch
|
| 14:00 to 14:30 |
Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
Jeff Xu |
| 14:30 to 15:00 |
Quantum Threshold is Powerful
Jackson Morris, Daniel Grier |
| 15:00 to 15:30 |
Coffee Break
|
| 15:30 to 16:00 |
On the Automatability of Tree-Like k-DNF Resolution
Gaia Carenini, Susanna de Rezende |
| 16:00 to 16:30 |
A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
Dmitry Sokolov, Anastasia Sofronova |
| 16:30 to 17:00 |
Provably Total Functions in the Polynomial Hierarchy
Noah Fleming, Christophe Marciot, Deniz Imrek |
| 17:00 |
Business Meeting (Internal)
|
| 09:00 to 09:30 |
From an odd arity signature to a Holant dichotomy
Boning Meng, Juqiu Wang, Mingji Xia, Jiayi Zheng |
| 09:30 to 10:00 |
Counting Martingales for Measure and Dimension in Complexity Classes
John Hitchcock, Adewale Sekoni, Hadi Shafei |
| 10:00 to 10:30 |
Coffee Break
|
| 10:30 to 11:00 |
Algebraic Pseudorandomness in VNC^0
Robert Andrews |
| 11:00 to 11:30 |
Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-in 3
Shubhangi Saraf, Devansh Shringi |
| 11:30 to 12:00 |
Algebraic metacomplexity and representation theory
Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Vladimir Lysikov |
| 12:00 to 14:00 |
Lunch
|
| 14:00 to 14:30 |
Improved separation between quantum and classical computers for sampling and functional tasks
Simon Marshall, Scott Aaronson, Vedran Dunjko |
| 14:30 to 15:00 |
New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
David Miloschewsky, Supartha Podder |
| 15:00 to 15:30 |
Coffee Break
|
| 15:30 to 16:00 |
Multiplicative Extractors for Samplable Distributions
Ronen Shaltiel |
| 16:00 to 16:30 |
How to Construct Random Strings
Oliver Korten, Rahul Santhanam |
| 16:30 to 17:00 |
Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs)
Marshall Ball, Lijie Chen, Roei Tell |
| 09:00 to 09:30 |
Characterizing the Distinguishability of Product Distributions through Multicalibration
Cassandra Marcussen, Aaron Putterman, Salil Vadhan |
| 09:30 to 10:00 |
Witness Encryption and NP-hardness of Learning
Halley Goldberg, Valentine Kabanets |
| 10:00 to 10:30 |
Coffee Break
|
| 10:30 to 11:00 |
Hardness Amplification for Real-Valued Functions
Yunqi Li, Prashant Nalini Vasudevan |
| 11:00 to 11:30 |
Near-Optimal Averaging Samplers and Matrix Samplers
Zhiyang Xun, David Zuckerman |
| 11:30 to 12:00 |
Pseudorandom bits for non-commutative programs
Chin Ho Lee, Emanuele Viola |
| 12:00 to 14:00 |
Lunch
|
| 14:00 to 14:30 |
Space-bounded quantum interactive proof systems
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang |
| 14:30 to 15:00 |
Directed st-connectivity with few paths is in quantum logspace
Roman Edenhofer, Simon Apers |
| 15:00 to 15:30 |
Coffee Break
|
| 15:30 to 16:00 |
List Decoding Quotient Reed-Muller Codes
Omri Gotlib, Tali Kaufman, Shachar Lovett |
| 16:00 to 16:30 |
Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products
Louis Golowich, Venkatesan Guruswami |
| 16:30 to 17:00 |
Tight bounds for stream decodable error-correcting codes
Meghal Gupta, Venkatesan Guruswami, Mihir Singhal |
| 17:00 |
Conclusion.
|
