default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, Volume 2025
Volume TR25, 2025
- Benny Applebaum, Oded Nir:
The Meta-Complexity of Secret Sharing. Article TR25-001 - Vinayak M. Kumar:
New Pseudorandom Generators and Correlation Bounds Using Extractors. Article TR25-002 - William Hoza:
Fooling Near-Maximal Decision Trees. Article TR25-003 - Songhua He:
A note on a hierarchy theorem for promise-BPTIME. Article TR25-004 - Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
SDPs and Robust Satisfiability of Promise CSP. Article TR25-005 - Subhash Khot, Kunal Mittal:
Biased Linearity Testing in the 1% Regime. Article TR25-006 - Amir Shpilka:
Improved Debordering of Waring Rank. Article TR25-007 - Shubhangi Saraf, Devansh Shringi:
Reconstruction of Depth $3$ Arithmetic Circuits with Top Fan-in $3$. Article TR25-008 - Marco Aldi, Sevag Gharibian, Dorian Rudolph:
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem. Article TR25-009 - Marshall Ball, Lijie Chen, Roei Tell:
Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs). Article TR25-010 - Oded Goldreich, Roei Tell:
Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems. Article TR25-011 - Dean Doron, Ori Fridman:
Bit-Fixing Extractors for Almost-Logarithmic Entropy. Article TR25-012 - Raghuvansh Saxena, Yael Tauman Kalai:
Polynomial Size, Short-Circuit Resilient Circuits for NC. Article TR25-013 - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh Saxena:
Information Dissemination via Broadcasts in the Presence of Adversarial Noise. Article TR25-014 - Abhibhav Garg, Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Ashutosh Shankar:
An exposition of recent list-size bounds of FRS Codes. Article TR25-015 - James Cook:
Another way to show $\mathrm{BPL} \subseteq \mathrm{CL}$ and $\mathrm{BPL} \subseteq \mathrm{P}$. Article TR25-016 - Ryan Williams:
Simulating Time in Square-Root Space. Article TR25-017 - Neekon Vafa, Vinod Vaikuntanathan:
Symmetric Perceptrons, Number Partitioning and Lattices. Article TR25-018 - Michal Koucký, Ian Mertz, Edward Pyne, Sasha Sami:
Collapsing Catalytic Classes. Article TR25-019 - Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola:
Pseudorandomness, symmetry, smoothing: I. Article TR25-020 - Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola:
Pseudorandomness, symmetry, smoothing: II. Article TR25-021 - Harm Derksen, Chin Ho Lee, Emanuele Viola:
Boosting uniformity in quasirandom groups: fast and simple. Article TR25-022 - Benny Applebaum, Eliran Kachlon:
How to Share an NP Statement or Combiners for Zero-Knowledge Proofs. Article TR25-023 - Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Lower Bounds Beyond DNF of Parities. Article TR25-024 - Hugo Aaronson, Gaia Carenini, Atreyi Chanda:
Property Testing in Bounded Degree Hypergraphs. Article TR25-025 - Siu On Chan, Hiu Tsun Ng:
How Random CSPs Fool Hierarchies: II. Article TR25-026 - Kuan Cheng, Ruiyang Wu:
Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions. Article TR25-027 - Satyadev Nandakumar, Subin Pulari, Akhil S, Suronjona Sarma:
One-Way Functions and Polynomial Time Dimension. Article TR25-028 - Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren:
PCP-free APX-Hardness of Nearest Codeword and Minimum Distance. Article TR25-029 - Oliver Korten, Toniann Pitassi, Russell Impagliazzo:
Stronger Cell Probe Lower Bounds via Local PRGs. Article TR25-030 - Shuichi Hirahara, Nobutaka Shimizu:
Error-Correction of Matrix Multiplication Algorithms. Article TR25-031 - Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse:
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. Article TR25-032 - Bruno Pasqualotto Cavalar, Igor C. Oliveira:
Boolean Circuit Complexity and Two-Dimensional Cover Problems. Article TR25-033 - Neha Kuntewar, Jayalal Sarma:
Range Avoidance in Boolean Circuits via Turan-type Bounds. Article TR25-034 - Abhibhav Garg, Rafael Mendes de Oliveira, Nitin Saxena:
Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals. Article TR25-035 - Siddharth Iyer:
Lifting for Arbitrary Gadgets. Article TR25-036 - Abhibhav Garg, Rafael Mendes de Oliveira, Akash Kumar Sengupta:
Uniform Bounds on Product Sylvester-Gallai Configurations. Article TR25-037 - Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Arina Smirnova:
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank Under NSETH and Beyond. Article TR25-038 - Klim Efremenko, Dmitry Itsykson:
Amortized Closure and Its Applications in Lifting for Resolution over Parities. Article TR25-039 - Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer:
Parallel Repetition for 3-Player XOR Games. Article TR25-040 - Igor Carboni Oliveira:
Meta-Mathematics of Computational Complexity Theory. Article TR25-041 - Robert Andrews, Deepanshu Kush, Roei Tell:
Polynomial-Time PIT from (Almost) Necessary Assumptions. Article TR25-042 - Shlomi Dolev:
Towards EXPTIME One Way Functions Bloom Filters, Succinct Graphs & Self Masking. Article TR25-043 - Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf:
Deterministic factorization of constant-depth algebraic circuits in subexponential time. Article TR25-044 - Marco Carmosino, Stefan Grosser:
Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap. Article TR25-045 - Gil Cohen, Leonard J. Schulman, Piyush Srivastava:
The Rate-Immediacy Barrier in Explicit Tree Code Constructions. Article TR25-046 - Michael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni, Mehtaab Sawhney:
Quasipolynomial bounds for the corners theorem. Article TR25-047 - Aryan Agarwala, Ian Mertz:
Bipartite Matching is in Catalytic Logspace. Article TR25-048 - Xin Li, Yan Zhong:
Range Avoidance and Remote Point for Low-Depth Circuits: New Algorithms and Hardness. Article TR25-049 - William Hoza, Zelin Lv:
On Sums of INW Pseudorandom Generators. Article TR25-050 - Abhibhav Garg, Rafael Mendes de Oliveira, Akash Kumar Sengupta:
Rank Bounds and PIT for $\Sigma^3 \Pi \Sigma \Pi^d$ circuits via a non-linear Edelstein-Kelly theorem. Article TR25-051 - Zeyu Guo, Siki Wang:
Deterministic Depth-4 PIT and Normalization. Article TR25-052 - Amir Shpilka:
On Approximate Symmetric Polynomials and Tightness of Homogenization Results. Article TR25-053 - Ronen Shaltiel:
Extractors for Samplable Distribution with Polynomially Small Min-Entropy. Article TR25-054 - Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, Antoine Vinciguerra:
Catalytic Computing and Register Programs Beyond Log-Depth. Article TR25-055 - Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan:
A Near-Optimal Polynomial Distance Lemma Over Boolean Slices. Article TR25-056 - Paul Beame, Michael Whitmeyer:
Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles. Article TR25-057 - Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan:
Generalised Linial-Nisan Conjecture is False for DNFs. Article TR25-058 - Emanuele Viola:
Communication complexity of pointer chasing via the fixed-set lemma. Article TR25-059 - Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov:
Sign-Rank of $k$-Hamming Distance is Constant. Article TR25-060 - Partha Mukhopadhyay, C. Ramya, Pratik Shastri:
Efficient Polynomial Identity Testing Over Nonassociative Algebras. Article TR25-061 - Prerona Chatterjee, Anamay Tengse:
Lower Bounds from Succinct Hitting Sets. Article TR25-062 - Robert Andrews:
Algebraic Pseudorandomness in VNC0. Article TR25-063 - Michael Jaber, Vinayak M. Kumar, David Zuckerman:
Linear Hashing Is Optimal. Article TR25-064 - Amnon Ta-Shma, Ben Chen:
Simplyfing Armoni's PRG. Article TR25-065 - Shuichi Hirahara, Nobutaka Shimizu:
An Optimal Error-Correcting Reduction for Matrix Multiplication. Article TR25-066 - Amnon Ta-Shma, Ben Chen:
Better Weighted Pseudorandom Generators Against Low Weight Read-Once Branching Programs. Article TR25-067 - Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan E. Prior, Ilya Volkovich:
Communication Complexity of Equality and Error Correcting Codes. Article TR25-068 - Noah Fleming, Christophe Marciot, Deniz Imrek:
Provably Total Functions in the Polynomial Hierarchy. Article TR25-069 - Halley Goldberg, Valentine Kabanets:
Witness Encryption and NP-hardness of Learning. Article TR25-070 - Chin Ho Lee, Emanuele Viola:
Pseudorandom bits for non-commutative programs. Article TR25-071 - Rahul Ilango, Alex Lombardi:
Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions. Article TR25-072 - Guangxu Yang, Jiapeng Zhang:
Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication. Article TR25-073 - Yaroslav Alekseev, Yuval Filmus:
Approximate polymorphisms of predicates. Article TR25-074 - Eshan Chattopadhyay, Jesse Goodman:
Leakage-Resilient Extractors against Number-on-Forehead Protocols. Article TR25-075 - Jan Seyfried, Sayantan Sen, Marco Tomamichel:
Testing (Conditional) Mutual Information. Article TR25-076 - Dean Doron, Edward Pyne, Roei Tell, Ryan Williams:
When Connectivity Is Hard, Random Walks Are Easy With Non-Determinism. Article TR25-077 - Yakov Shalunov:
Improved Bounds on the Space Complexity of Circuit Evaluation. Article TR25-078 - Amik Raj Behera, Nutan Limaye, Varun Ramanathan, Srikanth Srinivasan:
New Bounds for the Ideal Proof System in Positive Characteristic. Article TR25-079 - Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, Iddo Tzameret:
Lower Bounds against the Ideal Proof System in Finite Fields. Article TR25-080 - Guangxu Yang, Jiapeng Zhang:
Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication. Article TR25-081 - Per Austrin, Johan Håstad, Björn Martinsson:
On the usefulness of Promises. Article TR25-082 - C. S. Bhargav, Prateek Dwivedi, Nitin Saxena:
A primer on the closure of algebraic complexity classes under factoring. Article TR25-083 - Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf:
Closure under factorization from a result of Furstenberg. Article TR25-084 - Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf:
Constant-depth circuits for polynomial GCD over any characteristic. Article TR25-085 - Jiatu Li:
An Introduction to Feasible Mathematics and Bounded Arithmetic for Computer Scientists. Article TR25-086 - Yunqi Li, Prashant Nalini Vasudevan:
Hardness Amplification for Real-Valued Functions. Article TR25-087 - Igor Balla, Lianna Hambardzumyan, István Tomon:
Factorization norms and an inverse theorem for MaxCut. Article TR25-088 - Valentine Kabanets, Antonina Kolokolova:
Chain Rules for Time-Bounded Kolmogorov Complexity. Article TR25-089 - Noor Athamnah, Noga Ron-Zewi, Ron Rothblum:
Linear Prover IOPs in Log Star Rounds. Article TR25-090 - Tamer Mour, Alon Rosen, Ron Rothblum:
Tree PCPs. Article TR25-091 - Shuichi Hirahara, Mikito Nanashima:
Complexity-Theoretic Inductive Inference. Article TR25-092 - Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan:
Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications. Article TR25-093 - Shuichi Hirahara, Rahul Ilango, Bruno Loff:
Communication Complexity is NP-hard. Article TR25-094 - Rahul Ilango:
Godel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness. Article TR25-095 - Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan:
Searching for Falsified Clause in Random log{n}-CNFs is Hard for Randomized Communication. Article TR25-096 - Hadar Strauss:
On the Limits of Computationally Sound IPPs in the Isolated Model. Article TR25-097 - Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, Amit Sinhababu:
IPS Lower Bounds for Formulas and Sum of1 ROABPs. Article TR25-098 - Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff:
The Algebraic Cost of a Boolean Sum. Article TR25-099 - Mika Göös, Nathaniel Harms, Artur Riazanov:
Equality is Far Weaker Than Constant-Cost Communication. Article TR25-100 - Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett:
Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis. Article TR25-101 - Bruno Pasqualotto Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Monotone Circuit Complexity of Matching. Article TR25-102 - Rohit Gurjar, Kilian Rothmund, Thomas Thierauf:
2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs. Article TR25-103 - Oliver Korten, Rahul Santhanam:
How to Construct Random Strings. Article TR25-104 - Oded Goldreich, Guy N. Rothblum:
Location-Invariant Properties of Functions versus Properties of Distributions: United in Testing but Separated in Verification. Article TR25-105 - Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay:
Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth. Article TR25-106 - Justin Oh, Ronen Shaltiel:
Extractors for Samplable Distributions from the Two-Source Extractor Recipe. Article TR25-107 - Divesh Aggarwal, Pranjal Dutta, Saswata Mukherjee, Satyajeet Nagargoje, Maciej Obremski:
Efficient randomized strong 2-source non-malleable extractor for any linear min-entropy. Article TR25-108 - Dmitry Itsykson, Alexander Knop:
Supercritical Tradeoff Between Size and Depth for Resolution over Parities. Article TR25-116 - Uma Girish, Rocco A. Servedio:
Forrelation is Extremally Hard. Article TR25-117 - Farzan Byramji, Russell Impagliazzo:
Lower bounds for the Bit Pigeonhole Principle in Bounded-Depth Resolution over Parities. Article TR25-118 - John M. Hitchcock, Adewale Sekoni, Hadi Shafei:
Counting Martingales for Measure and Dimension in Complexity Classes. Article TR25-119 - Shuichi Hirahara, Naoto Ohsaka:
Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration. Article TR25-120 - Karthik Gajulapalli, Surendra Ghentiyala, Zeyong Li, Sidhant Saraogi:
Downward self-reducibility in the total function polynomial hierarchy. Article TR25-121 - Soumik Ghosh, Sathyawageeswar Subramanian, Wei Zhan:
Unconditional Pseudorandomness against Shallow Quantum Circuits. Article TR25-122 - Surendra Ghentiyala, Zeyong Li:
Hierarchies within TFNP: building blocks and collapses. Article TR25-123 - Marko Chalupa:
An AC0 Lower Bound for Random Satisfiable 3-CNF under Standard Random Restrictions. Article TR25-124 - Yanyi Liu, Rafael Pass:
Hardness Along the Boundary: Towards One-Way Functions from the Worst-case Hardness of Time-Bounded Kolmogorov Complexity. Article TR25-125 - Amey Bhangale, Silas Richelson:
Plane vs. Plane Low Degree Test. Article TR25-126 - Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche:
Proof Systems That Tightly Characterise Model Counting Algorithms. Article TR25-127 - Ian Orzel:
Computing the Elementary Symmetric Polynomials in Positive Characteristics. Article TR25-128 - Irit Dinur, Oded Goldreich:
Expansion without Connectivity: A Property Testing Perspective. Article TR25-129 - Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, Tom Gur:
Algorithmic Polynomial Freiman-Ruzsa Theorems. Article TR25-130 - Anand Kumar Narayanan:
Hyperdeterminants are hard in four dimensions. Article TR25-131 - Joshua Cook, Dana Moshkovitz:
Time and Space Efficient Deterministic List Decoding. Article TR25-132 - Pratik Shastri:
Lower Bounds for Noncommutative Circuits with Low Syntactic Degree. Article TR25-133 - Jiaqi Lu, Rahul Santhanam, Iddo Tzameret:
AC0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard. Article TR25-134 - Jules Armand, Prateek Dwivedi, Nutan Limaye, Magnus Rahbek Dalgaard Hansen, Srikanth Srinivasan, Sébastien Tavenas:
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs. Article TR25-135 - Sumegha Garg, Akash Sengupta:
Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes. Article TR25-136 - Scott Aaronson, Freek Witteveen:
Limits to black-box amplification in QMA. Article TR25-137 - Antoine Vinciguerra:
Linear Matroid Intersection is in Catalytic Logspace. Article TR25-138 - Kel Zin Tan, Prashant Nalini Vasudevan:
Improved Search-to-Decision Reduction for Random Local Functions. Article TR25-139 - Edward Pyne, Roei Tell:
Composing Low-Space Algorithms. Article TR25-140 - Lianna Hambardzumyan, Shachar Lovett, Morgan Shirley:
The Log-Rank Conjecture: New Equivalent Formulations. Article TR25-141 - Edward A. Hirsch, Ilya Volkovich:
Upper and Lower Bounds for the Linear Ordering Principle. Article TR25-142 - Vladimir Podolskii, Morgan E. Prior:
Alternation Depth of Threshold Decision Lists. Article TR25-143 - Siddhartha Jain, Vishnu Iyer, Rolando D. Somma, Ning Bao, Stephen P. Jordan:
Efficient Quantum Hermite Transform. Article TR25-144 - Sabee Grewal, William Kretschmer:
Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs. Article TR25-145 - Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang:
From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids. Article TR25-146 - Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan:
Decoding Balanced Linear Codes With Preprocessing. Article TR25-147 - Noah Singer:
Nine lower bound conjectures on streaming approximation algorithms for CSPs. Article TR25-148 - Leroy Chew, Tomás Peitl:
Strong (D)QBF Dependency Schemes via Pure Universal Resolution Paths. Article TR25-149 - James Cook, Surendra Ghentiyala, Ian Mertz, Edward Pyne, Nathan S. Sheffield:
The Structure of In-Place Space-Bounded Computation. Article TR25-150 - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
Constant Rate Codes for Adaptive Broadcasts Do Not Exist. Article TR25-151 - Tal Herman, Guy N. Rothblum:
Proving Natural Distribution Properties is Harder than Testing Them. Article TR25-152 - Isaac M. Hair, Amit Sahai:
SVP$_p$ is NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\epsilon} n}$. Article TR25-153 - Uma Girish:
Fourier Spectrum of Noisy Quantum Algorithms. Article TR25-154 - Young Kun Ko:
Lower Bounds for Linear Operators. Article TR25-155 - Young Kun Ko:
Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds. Article TR25-156 - Tejas Nareddy, Abhishek Mishra:
Recovery Reductions, Conjectures, and Barriers. Article TR25-157 - Fernando Granha Jeronimo, Nikhil Shagrithaya:
Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes. Article TR25-158 - Bonnie Berger, Rohan Goyal, Matthew M. Hong, Yael Tauman Kalai:
Efficiently Batching Unambiguous Interactive Proofs. Article TR25-159 - Yaroslav Alekseev, Nikita Gaevoy:
Intersection Theorems: A Potential Approach to Proof Complexity Lower Bounds. Article TR25-160 - Kunal Mittal:
Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics. Article TR25-161 - Ron D. Rothblum, Eden Florentz-Konopnicki:
Succinct Zero-knowledge Proofs from One-way Functions: The Blackbox Way. Article TR25-162 - Vinayak Kumar:
Most Juntas Saturate the Hardcore Lemma. Article TR25-163 - Jordan Horacsek, Chin Ho Lee, Igor Shinkar, Emanuele Viola, Renfei Zhou:
Constant-time source decoding. Article TR25-164 - Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard:
Ideals, Gröbner Bases, and PCPs. Article TR25-165 - Rohan Goyal, Venkatesan Guruswami:
Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes. Article TR25-166 - Tal Yankovitz:
CHS-alike 1/O(log log n)-rate tree codes from elementary binary shifts. Article TR25-167 - Tal Yankovitz:
Asymptotically good large-alphabet LDCs with polylogarithmic query complexity. Article TR25-168 - Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, Shubhangi Saraf:
On Proximity Gaps for Reed-Solomon Codes. Article TR25-169 - Soham Chatterjee, Prahladh Harsha, Mrinal Kumar:
Deterministic list decoding of Reed-Solomon codes. Article TR25-170 - Robert Andrews, Mrinal Kumar, Shanthanu S. Rai:
Modular composition & polynomial GCD in the border of small, shallow circuits. Article TR25-171 - Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett:
Restriction Trees for Sparsity and Applications. Article TR25-172 - Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer, Kunal Mittal:
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems. Article TR25-173 - Gil Cohen, Dean Doron, Noam Goldgraber, Tomer Manket:
Tracing AG Codes: Toward Meeting the Gilbert-Varshamov Bound. Article TR25-174 - John M. Hitchcock, Adewale Sekoni, Hadi Shafei:
Random Permutations in Computational Complexity. Article TR25-175 - John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, Mark Zhandry:
Separating QMA from QCMA with a classical oracle. Article TR25-176 - Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, Dmitry Sokolov:
Sampling Permutations with Cell Probes is Hard. Article TR25-177 - Sam Buss, Anant Dhayal, Valentine Kabanets, Antonina Kolokolova, Sasank Mouli:
A Logspace Constructive Proof of L=SL. Article TR25-178 - Gil Cohen, Itay Cohen:
Wide Replacement Products Meet Gray Codes: Toward Optimal Small-Bias Sets. Article TR25-179 - Ryan O'Donnell, Noah Singer:
Low-soundness direct-product testers and PCPs from Kaufman-Oppenheim complexes. Article TR25-180 - Bruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray, Taiga Hiroka, Tomoyuki Morimae:
On Cryptography and Distribution Verification, with Applications to Quantum Advantage. Article TR25-181 - Oded Goldreich:
Proving the PCP Theorem with 1.5 proof compositions (or yet another PCP construction). Article TR25-182 - Daniel Kane, Anthony Ostuni, Kewen Wu:
Symmetric Distributions from Shallow Circuits. Article TR25-183 - Lijie Chen, Yang Hu, Hanlin Ren:
New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String. Article TR25-184 - Renato Ferreira Pinto Jr., Diptaksho Palit, Sofya Raskhodnikova:
Computational Complexity in Property Testing. Article TR25-185 - Aran Nayebi:
Intrinsic Barriers and Practical Pathways for Human-AI Alignment: An Agreement-Based Complexity Analysis. Article TR25-186 - Jiatu Li:
On the Time Complexity of Feasible Proofs. Article TR25-187 - Klim Efremenko, Dmitry Itsykson:
Strong ETH Holds for Bounded-Depth Resolution over Parities. Article TR25-188 - Anakin Dey, Zeyu Guo:
Debordering Closure Results in Determinantal and Pfaffian Ideals. Article TR25-189 - Rahul Ilango:
The Oracle Derandomization Hypothesis is False (And More) Assuming No Natural Proofs. Article TR25-190 - Hanlin Ren, Yichuan Wang, Yan Zhong:
Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits. Article TR25-191 - Guy Goldberg, Tom Gur, Sidhant Saraogi:
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies. Article TR25-192 - Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan:
Pseudodeterministic Communication Complexity. Article TR25-193 - Rohan Goyal, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar:
Fast list recovery of univariate multiplicity and folded Reed-Solomon codes. Article TR25-194 - Hadar Strauss:
On the Power of Computationally Sound Interactive Proofs of Proximity. Article TR25-195 - Gil Cohen, Gal Maor:
Ultra-Sparse Expanders and the Free Method. Article TR25-196 - Anna Gál, Gillat Kol, Raghuvansh Saxena, Huacheng Yu:
Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length. Article TR25-197 - Ari Biswas, Mark Bun, Clément Canonne, Satchit Sivakumar:
Interactive Proofs For Distribution Testing With Conditional Oracles. Article TR25-198 - Clément Canonne, Sam Polgar, Aditya Vikram Singh, Aravind Thyagarajan, Joy Qiping Yang:
Verification of Statistical Properties: Redefining the Possible. Article TR25-199 - Oded Goldreich, Guy N. Rothblum:
On doubly-sublinear interactive proofs for distributions. Article TR25-200 - Oded Goldreich, Tal Herman, Guy N. Rothblum:
Interactive proof systems for FARNESS. Article TR25-201 - Yanyi Liu, Rafael Pass:
One-way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity. Article TR25-202 - Jinqiao Hu, Zhenjian Lu, Igor C. Oliveira:
Hardness of Computing Nondeterministic Kolmogorov Complexity. Article TR25-203 - Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, Weiqiang Yuan:
Total Search Problems in ZPP. Article TR25-204 - Fatemeh Ghasemi, Swastik Kopparty:
Fourier Sparsity of Delta Functions and Matching Vector PIRs. Article TR25-205 - Fatemeh Ghasemi, Gal Gross, Swastik Kopparty:
Permanental rank versus determinantal rank of random matrices over finite fields. Article TR25-206 - Madhu Sudan:
Algebra in Algorithmic Coding Theory. Article TR25-207 - Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, Geoffrey Mon:
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes. Article TR25-208 - Johan Håstad:
Efficiently finding small representations for LTFs. Article TR25-209 - Surendra Ghentiyala, Zeyong Li, Noah Stephens-Davidowitz:
Range avoidance, Arthur-Merlin, and TFNP. Article TR25-210 - Jinqiao Hu, Zhenjian Lu, Igor C. Oliveira:
Equivalence Between Coding and Complexity Lower Bounds. Article TR25-211 - Rohan Goyal, Venkatesan Guruswami:
Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes. Article TR25-212 - Tali Kaufman, David Mass:
Improved Small Set Expansion in High Dimensional Expanders. Article TR25-213 - Prasad Chaugule:
A new characterization of VNP via Colored Determinant. Article TR25-214 - Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira:
Synergies Between Complexity Theory and Nondeterministic Kolmogorov Complexity. Article TR25-215 - Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang:
Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs. Article TR25-216 - Tom Gur, Dor Minzer, Guy Weissenberg, Kai Zhe Zheng:
$3$-Query RLDCs are Strictly Stronger than $3$-Query LDCs. Article TR25-217 - Ari Biswas, Rajko Nenadov:
Refuting Perfect Matchings in Spectral Expanders is Hard. Article TR25-218 - Bruno Pasqualotto Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff:
Negations are powerful even in small depth. Article TR25-219 - Edward A. Hirsch, Ilya Volkovich:
A Note on Avoid vs MCSP. Article TR25-220 - Bruno Pasqualotto Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, Xingjian Li:
A Meta-Complexity Characterization of Minimal Quantum Cryptography. Article TR25-221 - Shubhangi Saraf, Devansh Shringi, Narmada Varadarajan:
Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-in. Article TR25-222
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-02 01:02 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.
