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