default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, Volume 2026
Volume TR26, 2026
- Théo Borém Fabris, Nutan Limaye, Srikanth Srinivasan, Amir Yehudayoff:
Multilinear Algebraic Branching Programs and the Min-Partition Rank Method. Article TR26-001 - Amik Raj Behera, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan:
Separation Results for Constant-Depth and Multilinear Ideal Proof Systems. Article TR26-002 - Swastik Kopparty:
Recovering polynomials over finite fields from noisy character values. Article TR26-003 - Ilya Volkovich:
Yet Another Proof that BPP ⊆ PH. Article TR26-004 - Matt Kovacs-Deak, Daochen Wang, Rain Zimin Yang:
Rational degree is polynomially related to degree. Article TR26-005 - Lijie Chen, Yichuan Wang:
Separating RAM and Multitape Turing Machines with Short Random Oracles. Article TR26-006 - Yaroslav Alekseev, Nikita Gaevoy:
New Polynomial-Depth Res(+) Lower Bounds. Article TR26-007 - Ran Raz:
A Note on Natural-Proofs for Super-Linear Lower Bounds for Linear Functions. Article TR26-008 - Clément Canonne:
A short note on (distribution) testing lower bounds via polynomials. Article TR26-009 - Sourav Chakraborty, Anna Gál:
Nearly Tight Bounds on the Block Number of Boolean Functions in Terms of Sensitivity. Article TR26-010 - Divesh Aggarwal, Zihan Li, Saswata Mukherjee, Maciej Obremski, João Ribeiro:
Complete Characterization of Randomness Extraction from DAG-Correlated Sources. Article TR26-011 - Johan Håstad:
Perfectly Satisfiable Systems of Linear Equations and Fixed Weight Solutions. Article TR26-012 - Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett:
Quantum-Classical Equivalence for AND-Functions. Article TR26-013 - Yipin Wang:
A Fourier-Analytic Switching Lemma over Fp and the AC0 Lower Bound for Generalized Parity. Article TR26-014 - Lijie Chen, Jiatu Li, Igor C. Oliveira, Ryan Williams:
A Theory for Probabilistic Polynomial-Time Reasoning. Article TR26-015 - Gil Cohen, Dean Doron, Noam Goldgraber:
Optimal PRGs for Low-Degree Polynomials over Polynomial-Size Fields. Article TR26-016 - Alon Dermer, Ronen Shaltiel:
Multiplicative Pseudorandom Generators for Nondeterministic Circuits. Article TR26-017 - Dmitry Itsykson, Vladimir Podolskii, Alexander Shekhovtsov:
Resolution Width Lifts to Near-Quadratic-Depth Res(⊕) Size. Article TR26-018 - Yang P. Liu, Shachar Lovett, Kunal Mittal:
Improved Parallel Repetition for GHZ-Supported Games via Spreadness. Article TR26-019 - John Bostanci, Andrew Huang, Vinod Vaikuntanathan:
Separating Quantum and Classical Advice with Good Codes. Article TR26-020 - Jinqiao Hu, Yahel Manor, Igor C. Oliveira:
Failure of Symmetry of Information for Randomized Computations. Article TR26-021 - Alexandra Henzinger, Edward Pyne, Seyoon Ragavan:
Catalytic Tree Evaluation From Matching Vectors. Article TR26-022 - Noah Fleming, Anna Gál, Christophe Marciot, Deniz Imrek:
Separations above TFNP from Sherali-Adams Lower Bounds. Article TR26-023 - Robert Andrews, Abhibhav Garg, Éric Schost:
Hilbert's Nullstellensatz is in the Counting Hierarchy. Article TR26-024 - 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? Article TR26-025 - Sanyam Agarwal, Sagnik Dutta, Anurag Pandey, Himanshu Shukla:
When Hilbert approximates: A Strong Nullstellensatz for Approximate Polynomial Satisfiability. Article TR26-026 - Vishnu Iyer, Siddhartha Jain, Stephen P. Jordan, Rolando D. Somma:
Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders. Article TR26-027 - Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan:
Weak Zero-Knowledge and One-Way Functions. Article TR26-028 - Amir Shpilka, Yann Tal:
Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree. Article TR26-029 - Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, Adi Shraibman:
Spiky Rank and Its Applications to Rigidity and Circuits. Article TR26-030 - Zihan Hao, Zikuan Huang, Qipeng Liu:
On the Need for (Quantum) Memory with Short Outputs. Article TR26-031 - Mrinal Kumar, Noga Ron-Zewi:
Advances in List Decoding of Polynomial Codes. Article TR26-032 - Emanuele Viola:
Simple XOR lemma. Article TR26-033 - Alexey Milovanov:
Limit on the computational power of ℂ-random strings. Article TR26-034 - Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Chandan Saha:
Learning Read-Once Determinants and the Principal Minor Assignment Problem. Article TR26-035 - Aminadav Chuyoon, Amir Shpilka:
On Factorization of Sparse Polynomials of Bounded Individual Degree. Article TR26-036 - Noga Ron-Zewi, Mor Weiss:
A Note on the Equivalence Between Zero-knowledge and Quantum CSS Codes. Article TR26-037 - Nobutaka Shimizu, Kenji Yasunaga:
Hardness Amplification Beyond Boolean Functions. Article TR26-038 - Lijie Chen, Avishay Tal, Yichuan Wang:
Super-quadratic Lower Bounds for Depth-2 Linear Threshold Circuits. Article TR26-039 - Zach Hunter, Aleksa Milojevic, Benny Sudakov, István Tomon:
Communication Complexity of Disjointness under Product Distributions. Article TR26-040 - Nikolai Chukhin:
A Note on Conditional Complexity Hardness of Matrix Rigidity and Tensor Rank. Article TR26-041 - Prateek P. Kulkarni:
Entanglement-Dependent Error Bounds for Hamiltonian Simulation. Article TR26-042 - Deepanshu Kush:
An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds. Article TR26-043 - Vahid R. Asadi, Richard Cleve:
Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling. Article TR26-044 - Edward Pyne, Roei Tell:
Using Hardness vs Randomness to Design Low-Space Algorithms. Article TR26-045 - Xinyu Mao, Jiapeng Zhang:
Black-Box Separation Between Multi-Collision Resistance and Collision Resistance. Article TR26-046 - Young Kun Ko:
An Ω((log n / log log n)2) Cell-Probe Lower Bound for Dynamic Boolean Data Structures. Article TR26-047 - Shuichi Hirahara, Nobutaka Shimizu:
Optimal Random Self-Reductions for All Linear Problems. Article TR26-048 - Mika Göös, Nathaniel Harms, Florian Richter, Anastasia Sofronova:
No Constant-Cost Protocol for Point-Line Incidence. Article TR26-049 - Gal Arnon, Noam Mazor, Rafael Pass, Jad Silbak:
Witness-Indistinguishable Arguments of Knowledge and One-Way Functions. Article TR26-050 - Yanyi Liu, Noam Mazor, Rafael Pass:
Cryptographic Implications of Worst-Case Hardness of Time-Bounded Kolmogorov Complexity. Article TR26-051 - Shuichi Hirahara, Mikito Nanashima:
A Sharp Characterization of Pessiland. Article TR26-052 - Lance Fortnow:
How Does Machine Learning Manage Complexity? Article TR26-053 - Noah Singer, Madhur Tulsiani, Santhoshini Velusamy:
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs. Article TR26-054 - Ben Davis, Robert Robere:
Res(log) Proves Bounded-Depth Frege Lower Bounds. Article TR26-055 - Florian Frick, Kaave Hosseini, Aliaksei Vasileuski:
A ℤ2-Topological Framework for Sign-rank Lower Bounds. Article TR26-056 - Rohan Goyal, Venkatesan Guruswami, Jun-Ting Hsieh:
Explicit Constant-Alphabet Subspace Design Codes. Article TR26-057 - Zeyu Guo, Roshan Raj, Chong Shangguan, Zihan Zhang:
Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets. Article TR26-058 - Yevgeniy Dodis, Shachar Lovett, Daniel Wichs:
Locally Computable High Independence Hashing. Article TR26-059 - Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang:
White-Box Adversarial Streaming Lower Bounds beyond Two-Party Communication. Article TR26-060 - Ran Raz:
Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings. Article TR26-061 - Hunter Monroe:
Toward a Characterization of Simulation Between Arithmetic Theories. Article TR26-062 - Pritish Kamath, Ravi Kumar, Pasin Manurangsi:
When Majority Fails: Tight Bounds for Correlation Distillation Conjectures. Article TR26-063 - Ben Chen, Gil Cohen, Dean Doron, Yuval Khaskelberg, Amnon Ta-Shma:
Toward Improving Nisan's PRG via Deweightization. Article TR26-064 - Nir Shalmon, Amir Shpilka:
Partial Derivative Complexity of a Product of Linearly Independent Quadratics. Article TR26-065 - Mohammad Mahdi Khodabandeh, Igor Shinkar:
On Sampling Lower Bounds for Polynomials. Article TR26-066 - Nir Bitansky, Noam Mazor:
Secret-Key PIR from One-Way Functions. Article TR26-067 - John M. Hitchcock:
Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time. Article TR26-068 - Shachar Lovett, Raghu Meka, Yimeng Wang:
Moonflowers and efficient code sparsification. Article TR26-069 - Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret:
Hard CNF Instances for Ideal Proof Systems. Article TR26-070 - Archit Chauhan, Rohit Gurjar, Kilian Rothmund, Thomas Thierauf:
Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist. Article TR26-071 - Robert Andrews, Abhibhav Garg:
An Improved Construction of Variety-Evasive Subspace Families. Article TR26-072 - Vishwas Bhargava, Leonard J. Schulman, Shiri Sivan:
An Algorithmic Proof of Kruskal's Tensor Decomposition Theorem. Article TR26-073 - Rohan Goyal, Venkatesan Guruswami:
Improved analysis of list-decodability of random linear codes: It's all about counting constraints. Article TR26-074 - Farzan Byramji, Daniel Kane, Jackson Morris, Anthony Ostuni:
On the Advantage of Adaptivity for Sampling with Cell Probes. Article TR26-075 - Nimrod Kaplan, Amir Shpilka:
Polynomial Identity Testing for Read-4 Arithmetic Formulas. Article TR26-076 - Joshua Brakensiek, Venkatesan Guruswami:
Redundancy Is All You Need (for CSP Sparsification). Article TR26-077 - Susanna F. de Rezende, David Engström, Yassine Ghannane, Kilian Risse:
Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size. Article TR26-078 - Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Erasmo Tani:
On the LSH Distortion of Ulam and Cayley Similarities. Article TR26-079 - Srijan Chakraborty, Samir Datta, Aryan Kusre, Partha Mukhopadhyay, Amit Sinhababu:
Maximum Matching and Related Problems in Catalytic Logspace. Article TR26-080 - Farzan Byramji, Daniel Kane, Jackson Morris, Anthony Ostuni:
Hard-to-Sample Distributions from Robust Extractors. Article TR26-081 - Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Pseudorandomness Beating the Hybrid Argument for Insensitive Algorithms. Article TR26-082 - Nicholas Smirnov:
Boolean Derivative Certificates and Maximal ANF Terms. Article TR26-083 - Abhibhav Garg, Rafael Mendes de Oliveira, Akash Kumar Sengupta, Nir Shalmon, Amir Shpilka:
Rank bounds and polynomial-time PIT for ΣkΠΣΠ2 circuits. Article TR26-084 - Sujoy Bhore, Archit Chauhan, Rohit Gurjar, Himanshi Singh:
On Parallel Complexity of Arboricity in Structured Graphs. Article TR26-085 - Nader H. Bshouty:
A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing. Article TR26-086 - Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Alessandro Panconesi, Erasmo Tani, Andrew Tomkins:
Tight Bounds for Sketching Intersecting Sets, with Applications. Article TR26-087 - Oded Goldreich:
A digest of the work of Rothblum, Vadhan, and Wigderson (2013). Article TR26-088 - Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Yunya Zhao:
Near Optimal Extractors for Samplable Sources under Nondeterministic Hardness. Article TR26-089 - Pruthvi Boyapati, Suryajith Chillara, Pratyush Vempati:
Multilinear Formula Lower Bounds for Sparse Determinants. Article TR26-090 - Halley Goldberg, Mandar Juvekar, Valentine Kabanets:
Non-Levin NP-Hardness of Implicit MCSP and PAC Learning under Few Assumptions. Article TR26-091 - Guangxu Yang:
Exponential Quantum Space Advantage for Approximating Max-kSAT in the Streaming Setting. Article TR26-092 - Dean Doron, Oded Goldreich:
Seven observations about weighted pseudorandom generators. Article TR26-094 - Divesh Aggarwal, Rishav Gupta, Hai Hoang Nguyen, Kel Zin Tan, Prashant Nalini Vasudevan:
Towards Worst-case Hardness for Low-Noise LPN. Article TR26-095 - Emanuele Viola:
The dream XOR lemma is false. Article TR26-096 - Karthik Sheshadri:
A symmetric determinantal lower bound for diagonal power sums via polar degree. Article TR26-097 - Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, Surya Mathialagan:
SNARGs for NP from Unprovability of Mathematical Theorems. Article TR26-098 - Pravesh Kothari:
Kikuchi Graphs of Random Hypergraphs are Approximately Johnson. Article TR26-099 - Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Thomas Thierauf:
Bipartite Matching is in NC. Article TR26-100 - Sravanthi Chede, Leroy Chew, Vaibhav Krishan, Anil Shukla:
On Proof Systems for #QBF. Article TR26-101 - Liyan Chen, Matthew M. Hong, Yael Tauman Kalai, Zoe Xi:
Towards a Doubly E?cient IP=PSPACE. Article TR26-102 - Avishay Tal, Weiqiang Yuan:
Quantum Advantage in Tolerant Junta Testing. Article TR26-103
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-08-04 00:41 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.
