default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID41st CCC 2026: Lisbon, Portugal
- Dana Moshkovitz
:
41st Computational Complexity Conference, CCC 2026, Lisbon, Portugal, August 3-6, 2026. LIPIcs 383, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2026, ISBN 978-3-95977-437-6 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xviii
- Rishav Gupta, Bingkai Lin, Xin Zheng:
Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding Under ETH. 1:1-1:17 - Aaron Putterman, Salil P. Vadhan, Vadim Zaripov:
Bounded-Independence Sampling of Edges for Combinatorial Graph Properties. 2:1-2:22 - Yakov Shalunov:
Improved Bounds on the Space Complexity of Circuit Evaluation. 3:1-3:13 - Baocheng Sun, Thomas Vidick:
Probabilistically Checking Quantum Proofs, with Interaction. 4:1-4:49 - Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco A. Servedio:
Condensing and Extracting Against Online Adversaries. 5:1-5:22 - Yang P. Liu, Shachar Lovett, Kunal Mittal:
Improved Parallel Repetition for GHZ-Supported Games via Spreadness. 6:1-6:21 - Lianna Hambardzumyan, Shachar Lovett, Morgan Shirley:
The Log-Rank Conjecture: New Equivalent Formulations. 7:1-7:9 - Erfan Khaniki, Ján Pich, Dmitry Sokolov:
Efficient Adversaries. 8:1-8:32 - Jinqiao Hu, Zhenjian Lu, Igor C. Oliveira:
Hardness of Computing Nondeterministic Kolmogorov Complexity. 9:1-9:50 - Gil Cohen, Leonard J. Schulman, Piyush Srivastava:
The Rate-Immediacy Barrier in Explicit Tree Code Constructions. 10:1-10:22 - Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, Jiaheng Wang:
Beyond Bilinear Complexity: What Works and What Breaks with Many Modes? 11:1-11:23 - Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen:
Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-To-Hamiltonian Constructions. 12:1-12:35 - Dmitry Itsykson, Vladimir Podolskii, Alexander Shekhovtsov:
Resolution Width Lifts to Near-Quadratic-Depth Res(⊕) Size. 13:1-13:27 - Guy Moshkovitz, Dora Woodruff:
A Weak Regularity Lemma for Polynomials. 14:1-14:24 - Thiago Bergamaschi, Tony Metger, Thomas Vidick, Tina Zhang:
Derandomised Tensor Product Gap Amplification for Quantum Hamiltonians. 15:1-15:22 - Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf:
Constant-Depth Circuits for Polynomial GCD over Any Characteristic. 16:1-16:21 - Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta, Nir Shalmon, Amir Shpilka:
Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² Circuits. 17:1-17:18 - Alon Dermer, Ronen Shaltiel:
Multiplicative Pseudorandom Generators for Nondeterministic Circuits. 18:1-18:20 - Sanyam Agarwal, Sagnik Dutta, Anurag Pandey, Himanshu Shukla:
When Hilbert Approximates: A Strong Nullstellensatz for Approximate Polynomial Satisfiability. 19:1-19:18 - Aminadav Chuyoon, Amir Shpilka:
On Factorization of Sparse Polynomials of Bounded Individual Degree. 20:1-20:20 - Gil Cohen, Itay Cohen:
Wide Replacement Products Meet Gray Codes: Toward Optimal Small-Bias Sets. 21:1-21:27 - Théo Borém Fabris, Nutan Limaye, Srikanth Srinivasan, Amir Yehudayoff:
Multilinear Algebraic Branching Programs and the Min-Partition Rank Method. 22:1-22:20 - Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett:
Quantum-Classical Equivalence for And-Functions. 23:1-23:24 - Sarah Bordage, Alessandro Chiesa, Ziyi Guan, Ignacio Manzur:
All Polynomial Generators Preserve Distance with Mutual Correlated Agreement. 24:1-24:18 - Nimrod Kaplan, Amir Shpilka:
Polynomial Identity Testing for Read-4 Arithmetic Formulas. 25:1-25:18 - Max Hopkins, Arka Ray:
A Simple Sub-Polynomial Degree Coboundary Expander. 26:1-26:41 - Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher D. Rosin, Navid Talebanfard:
Optimal Depth-Three Circuits for Inner Product. 27:1-27:25 - Matthias Christandl, Aram W. Harrow, Greta Panova, Pietro M. Posta, Michael Walter:
Plethysm is in #BQP. 28:1-28:11 - Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, Ninad Rajgopal:
Frontier Space-Time Algorithms Using Only Full Memory. 29:1-29:23 - Chandrima Kayal, Rajat Mittal, Sai Soumya Nalli, Manaswi Paraashar, Karthikeya Polisetty, Jayalal Sarma, Nitin Saurabh:
Bounds for Hardness Condensation in the Query Model. 30:1-30:20 - Esty Kelman, Uri Meir, Kai Zhe Zheng:
Optimal Testing of Reed-Muller Codes with an Online Adversary. 31:1-31:26 - M. Levent Dogan, John Maar, Rafael Oliveira, Youming Qiao:
Fixed-Parameter Degree Bounds and Complexity of the Orbit Closure Intersection Problem for Tensors. 32:1-32:21 - Pruthvi Boyapati, Suryajith Chillara, Pratyush Vempati:
Multilinear Formula Lower Bounds for Sparse Determinants. 33:1-33:21 - Avishay Tal, Weiqiang Yuan:
Quantum Advantage in Tolerant Junta Testing. 34:1-34:17 - Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch:
Trace Hermitian Codes Have Vanishing Bias. 35:1-35:28 - Josh Alman, Baitian Li:
Asymptotic Rank Speedup Theorems, Revisited. 36:1-36:42 - Noah Fleming, Anna Gál, Deniz Imrek, Christophe Marciot:
Separations Above TFNP from Sherali-Adams Lower Bounds. 37:1-37:23 - Jon Nelson, Joel Rajakumar, Michael J. Gullans:
Non-Clifford Gates Are Required for Long-Term Memory. 38:1-38:13 - Shalev Ben-David, Mohammad Hossein Ebtehaj:
Faux Determinism. 39:1-39:25 - Bruno Cavalar, Susanna F. de Rezende, Matthew Gray, Rahul Santhanam:
ETH-Hardness of Learning Monotone Circuits and Approximating Their Size. 40:1-40:25 - Sumegha Garg, Songhua He, Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang:
Systematic Data Structure Lower Bounds via the Query-With-Sketch Model. 41:1-41:44 - Fedor Kiselev:
Randomized Separations in Black-Box TFNP. 42:1-42:17
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2026-07-24 23:10 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated, funded, and maintained by:
Schloss Dagstuhl - Leibniz Center for Informatics is a member of the Leibniz Association and is funded by the federal government of Germany and the states of Germany, especially Saarland and Rhineland‑Palatinate.
