CCC A

38 papers

YearTitle / Authors
202540th Computational Complexity Conference, CCC 2025, Toronto, Canada, August 5-8, 2025
Srikanth Srinivasan
2025A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion.
Anastasia Sofronova, Dmitry Sokolov
2025A Min-Entropy Approach to Multi-Party Communication Lower Bounds.
Mi-Ying (Miryam) Huang, Xinyu Mao, Shuo Wang, Guangxu Yang, Jiapeng Zhang
2025Algebraic Metacomplexity and Representation Theory.
Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Vladimir Lysikov
2025Algebraic Pseudorandomness in VNC⁰.
Robert Andrews
2025Amortized Closure and Its Applications in Lifting for Resolution over Parities.
Klim Efremenko, Dmitry Itsykson
2025Biased Linearity Testing in the 1% Regime.
Subhash Khot, Kunal Mittal
2025Characterizing the Distinguishability of Product Distributions Through Multicalibration.
Cassandra Marcussen, Aaron Putterman, Salil P. Vadhan
2025Counting Martingales for Measure and Dimension in Complexity Classes.
John M. Hitchcock, Adewale Sekoni, Hadi Shafei
2025Direct Sums for Parity Decision Trees.
Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, Weiqiang Yuan
2025Directed st-Connectivity with Few Paths Is in Quantum Logspace.
Simon Apers, Roman Edenhofer
2025From an Odd Arity Signature to a Holant Dichotomy.
Boning Meng, Juqiu Wang, Mingji Xia, Jiayi Zheng
2025Front Matter, Table of Contents, Preface, Conference Organization.
2025Generalised Linial-Nisan Conjecture Is False for DNFs.
Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan
2025Hardness Amplification for Real-Valued Functions.
Yunqi Li, Prashant Nalini Vasudevan
2025Hardness of Clique Approximation for Monotone Circuits.
Jaroslaw Blasiok, Linus Meierhöfer
2025How to Construct Random Strings.
Oliver Korten, Rahul Santhanam
2025Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks.
Simon C. Marshall, Scott Aaronson, Vedran Dunjko
2025Lifting with Colourful Sunflowers.
Susanna F. de Rezende, Marc Vinyals
2025List Decoding Quotient Reed-Muller Codes.
Omri Gotlib, Tali Kaufman, Shachar Lovett
2025Multiplicative Extractors for Samplable Distributions.
Ronen Shaltiel
2025Near-Optimal Averaging Samplers and Matrix Samplers.
Zhiyang Xun, David Zuckerman
2025New Codes on High Dimensional Expanders.
Irit Dinur, Siqi Liu, Rachel Yun Zhang
2025New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements.
David Miloschewsky, Supartha Podder
2025On the Automatability of Tree-Like k-DNF Resolution.
Gaia Carenini, Susanna F. de Rezende
2025Online Condensing of Unpredictable Sources via Random Walks.
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman
2025Provably Total Functions in the Polynomial Hierarchy.
Noah Fleming, Deniz Imrek, Christophe Marciot
2025Pseudorandom Bits for Non-Commutative Programs.
Chin Ho Lee, Emanuele Viola
2025Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products.
Louis Golowich, Venkatesan Guruswami
2025Quantum Threshold Is Powerful.
Daniel Grier, Jackson Morris
2025Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-In 3.
Shubhangi Saraf, Devansh Shringi
2025Space-Bounded Quantum Interactive Proof Systems.
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang
2025Sparser Abelian High Dimensional Expanders.
Yotam Dikstein, Siqi Liu, Avi Wigderson
2025Super-Critical Trade-Offs in Resolution over Parities via Lifting.
Arkadev Chattopadhyay, Pavel Dvorák
2025Switching Graph Matrix Norm Bounds: From i.i.d. to Random Regular Graphs.
Jeff Xu
2025Tight Bounds for Stream Decodable Error-Correcting Codes.
Meghal Gupta, Venkatesan Guruswami, Mihir Singhal
2025Towards Free Lunch Derandomization from Necessary Assumptions (And OWFs).
Marshall Ball, Lijie Chen, Roei Tell
2025Witness Encryption and NP-Hardness of Learning.
Halley Goldberg, Valentine Kabanets