Computational Complexity Conference
CCC 2025 Accepted Papers

CCC 2025 Accepted Papers

Omri Gotlib, Tali Kaufman, Shachar Lovett. List Decoding Quotient Reed-Muller Codes
Yunqi Li, Prashant Nalini Vasudevan. Hardness Amplification for Real-Valued Functions
Jackson Morris, Daniel Grier. Quantum Threshold is Powerful
Jarosław Błasiok, Linus Meierhöfer. Hardness of clique approximation for monotone circuits
Simon Marshall, Scott Aaronson, Vedran Dunjko. Improved separation between quantum and classical computers for sampling and functional tasks
Zhiyang Xun, David Zuckerman. Near-Optimal Averaging Samplers and Matrix Samplers
Yotam Dikstein, Siqi Liu, Avi Wigderson. Sparser Abelian High Dimensional Expanders
Klim Efremenko, Dmitry Itsykson. Amortized Closure and Its Applications in Lifting for Resolution over Parities
Chin Ho Lee, Emanuele Viola . Pseudorandom bits for non-commutative programs
Subhash Khot, Kunal Mittal. Biased Linearity Testing in the 1% Regime
Jeff Xu. Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
David Miloschewsky, Supartha Podder. New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
Meghal Gupta, Venkatesan Guruswami, Mihir Singhal. Tight bounds for stream decodable error-correcting codes
Gaia Carenini, Susanna de Rezende. On the Automatability of Tree-Like k-DNF Resolution
Robert Andrews. Algebraic Pseudorandomness in VNC^0
Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, Weiqiang Yuan. Direct Sum for Parity Decision Trees
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang. Space-bounded quantum interactive proof systems
Roman Edenhofer, Simon Apers. Directed st-connectivity with few paths is in quantum logspace
Cassandra Marcussen, Aaron Putterman, Salil Vadhan. Characterizing the Distinguishability of Product Distributions through Multicalibration
John Hitchcock, Adewale Sekoni, Hadi Shafei. Counting Martingales for Measure and Dimension in Complexity Classes
Shubhangi Saraf, Devansh Shringi. Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-in 3
Ronen Shaltiel. Multiplicative Extractors for Samplable Distributions
Boning Meng, Juqiu Wang, Mingji Xia, Jiayi Zheng. From an odd arity signature to a Holant dichotomy
Arkadev Chattopadhyay, Pavel Dvořák. Super-critical Trade-offs in Resolution over Parities Via Lifting
Louis Golowich, Venkatesan Guruswami. Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products
Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Vladimir Lysikov. Algebraic metacomplexity and representation theory
Rachel Yun Zhang, Siqi Liu, Irit Dinur. New Codes on High Dimensional Expanders
Noah Fleming, Christophe Marciot, Deniz Imrek. Provably Total Functions in the Polynomial Hierarchy
Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan. Generalised Linial-Nisan Conjecture is False for DNFs
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman. Online Condensing of Unpredictable Sources via Random Walks
Marshall Ball, Lijie Chen, Roei Tell. Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs)
Dmitry Sokolov, Anastasia Sofronova. A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
Mi-Ying Huang, Xinyu Mao, Shuo Wang, Guangxu Yang, Jiapeng Zhang. A Min-Entropy Approach to Multi-Party Communication Lower Bounds
Halley Goldberg, Valentine Kabanets. Witness Encryption and NP-hardness of Learning
Oliver Korten, Rahul Santhanam. How to Construct Random Strings
Susanna de Rezende, Marc Vinyals. Lifting with Colourful Sunflowers