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. - Vinayak M. Kumar:
New Pseudorandom Generators and Correlation Bounds Using Extractors. - William Hoza:
Fooling Near-Maximal Decision Trees. - Songhua He:
A note on a hierarchy theorem for promise-BPTIME. - Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
SDPs and Robust Satisfiability of Promise CSP. - Subhash Khot, Kunal Mittal:
Biased Linearity Testing in the 1% Regime. - Amir Shpilka:
Improved Debordering of Waring Rank. - Shubhangi Saraf, Devansh Shringi:
Reconstruction of Depth $3$ Arithmetic Circuits with Top Fan-in $3$. - Marco Aldi, Sevag Gharibian, Dorian Rudolph:
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem. - Marshall Ball, Lijie Chen, Roei Tell:
Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs). - Oded Goldreich, Roei Tell:
Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems. - Dean Doron, Ori Fridman:
Bit-Fixing Extractors for Almost-Logarithmic Entropy. - Raghuvansh Saxena, Yael Tauman Kalai:
Polynomial Size, Short-Circuit Resilient Circuits for NC. - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh Saxena:
Information Dissemination via Broadcasts in the Presence of Adversarial Noise. - Abhibhav Garg, Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Ashutosh Shankar:
An exposition of recent list-size bounds of FRS Codes. - James Cook:
Another way to show $\mathrm{BPL} \subseteq \mathrm{CL}$ and $\mathrm{BPL} \subseteq \mathrm{P}$. - Ryan Williams:
Simulating Time in Square-Root Space. - Neekon Vafa, Vinod Vaikuntanathan:
Symmetric Perceptrons, Number Partitioning and Lattices. - Michal Koucký, Ian Mertz, Edward Pyne, Sasha Sami:
Collapsing Catalytic Classes. - Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola:
Pseudorandomness, symmetry, smoothing: I. - Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola:
Pseudorandomness, symmetry, smoothing: II. - Harm Derksen, Chin Ho Lee, Emanuele Viola:
Boosting uniformity in quasirandom groups: fast and simple. - Benny Applebaum, Eliran Kachlon:
How to Share an NP Statement or Combiners for Zero-Knowledge Proofs. - Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Lower Bounds Beyond DNF of Parities. - Hugo Aaronson, Gaia Carenini, Atreyi Chanda:
Property Testing in Bounded Degree Hypergraphs. - Siu On Chan, Hiu Tsun Ng:
How Random CSPs Fool Hierarchies: II. - Kuan Cheng, Ruiyang Wu:
Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions. - Satyadev Nandakumar, Subin Pulari, Akhil S, Suronjona Sarma:
One-Way Functions and Polynomial Time Dimension. - Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren:
PCP-free APX-Hardness of Nearest Codeword and Minimum Distance. - Oliver Korten, Toniann Pitassi, Russell Impagliazzo:
Stronger Cell Probe Lower Bounds via Local PRGs. - Shuichi Hirahara, Nobutaka Shimizu:
Error-Correction of Matrix Multiplication Algorithms. - Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse:
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. - Bruno Pasqualotto Cavalar, Igor C. Oliveira:
Boolean Circuit Complexity and Two-Dimensional Cover Problems. - Neha Kuntewar, Jayalal Sarma:
Range Avoidance in Boolean Circuits via Turan-type Bounds. - Abhibhav Garg, Rafael Mendes de Oliveira, Nitin Saxena:
Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals. - Siddharth Iyer:
Lifting for Arbitrary Gadgets. - Abhibhav Garg, Rafael Mendes de Oliveira, Akash Kumar Sengupta:
Uniform Bounds on Product Sylvester-Gallai Configurations. - Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Arina Smirnova:
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank Under NSETH and Beyond. - Klim Efremenko, Dmitry Itsykson:
Amortized Closure and Its Applications in Lifting for Resolution over Parities. - Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer:
Parallel Repetition for 3-Player XOR Games. - Igor Carboni Oliveira:
Meta-Mathematics of Computational Complexity Theory. - Robert Andrews, Deepanshu Kush, Roei Tell:
Polynomial-Time PIT from (Almost) Necessary Assumptions. - Shlomi Dolev:
Towards EXPTIME One Way Functions Bloom Filters, Succinct Graphs & Self Masking. - Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf:
Deterministic factorization of constant-depth algebraic circuits in subexponential time. - Marco Carmosino, Stefan Grosser:
Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap. - Gil Cohen, Leonard J. Schulman, Piyush Srivastava:
The Rate-Immediacy Barrier in Explicit Tree Code Constructions. - Michael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni, Mehtaab Sawhney:
Quasipolynomial bounds for the corners theorem. - Aryan Agarwala, Ian Mertz:
Bipartite Matching is in Catalytic Logspace. - Xin Li, Yan Zhong:
Range Avoidance and Remote Point for Low-Depth Circuits: New Algorithms and Hardness. - William Hoza, Zelin Lv:
On Sums of INW Pseudorandom Generators. - 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. - Zeyu Guo, Siki Wang:
Deterministic Depth-4 PIT and Normalization. - Amir Shpilka:
On Approximate Symmetric Polynomials and Tightness of Homogenization Results. - Ronen Shaltiel:
Extractors for Samplable Distribution with Polynomially Small Min-Entropy. - Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, Antoine Vinciguerra:
Catalytic Computing and Register Programs Beyond Log-Depth. - Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan:
A Near-Optimal Polynomial Distance Lemma Over Boolean Slices. - Paul Beame, Michael Whitmeyer:
Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles. - Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Artur Riazanov, Dmitry Sokolov, Weiqiang Yuan:
Generalised Linial-Nisan Conjecture is False for DNFs. - Emanuele Viola:
Communication complexity of pointer chasing via the fixed-set lemma. - Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov:
Sign-Rank of $k$-Hamming Distance is Constant. - Partha Mukhopadhyay, C. Ramya, Pratik Shastri:
Efficient Polynomial Identity Testing Over Nonassociative Algebras. - Prerona Chatterjee, Anamay Tengse:
Lower Bounds from Succinct Hitting Sets. - Robert Andrews:
Algebraic Pseudorandomness in VNC0. - Michael Jaber, Vinayak M. Kumar, David Zuckerman:
Linear Hashing Is Optimal. - Amnon Ta-Shma, Ben Chen:
Simplyfing Armoni's PRG. - Shuichi Hirahara, Nobutaka Shimizu:
An Optimal Error-Correcting Reduction for Matrix Multiplication. - Amnon Ta-Shma, Ben Chen:
Better Weighted Pseudorandom Generators Against Low Weight Read-Once Branching Programs. - Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan E. Prior, Ilya Volkovich:
Communication Complexity of Equality and Error Correcting Codes. - Noah Fleming, Christophe Marciot, Deniz imrek:
Provably Total Functions in the Polynomial Hierarchy. - Halley Goldberg, Valentine Kabanets:
Witness Encryption and NP-hardness of Learning. - Chin Ho Lee, Emanuele Viola:
Pseudorandom bits for non-commutative programs. - Rahul Ilango, Alex Lombardi:
Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions. - Guangxu Yang, Jiapeng Zhang:
Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication. - Yaroslav Alekseev, Yuval Filmus:
Approximate polymorphisms of predicates. - Eshan Chattopadhyay, Jesse Goodman:
Leakage-Resilient Extractors against Number-on-Forehead Protocols. - Jan Seyfried, Sayantan Sen, Marco Tomamichel:
Testing (Conditional) Mutual Information. - Dean Doron, Edward Pyne, Roei Tell, Ryan Williams:
When Connectivity Is Hard, Random Walks Are Easy With Non-Determinism. - Yakov Shalunov:
Improved Bounds on the Space Complexity of Circuit Evaluation. - Amik Raj Behera, Nutan Limaye, Varun Ramanathan, Srikanth Srinivasan:
New Bounds for the Ideal Proof System in Positive Characteristic. - Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, Iddo Tzameret:
Lower Bounds against the Ideal Proof System in Finite Fields. - Guangxu Yang, Jiapeng Zhang:
Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication. - Per Austrin, Johan Håstad, Björn Martinsson:
On the usefulness of Promises. - C. S. Bhargav, Prateek Dwivedi, Nitin Saxena:
A primer on the closure of algebraic complexity classes under factoring. - Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf:
Closure under factorization from a result of Furstenberg. - Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf:
Constant-depth circuits for polynomial GCD over any characteristic. - Jiatu Li:
An Introduction to Feasible Mathematics and Bounded Arithmetic for Computer Scientists. - Yunqi Li, Prashant Nalini Vasudevan:
Hardness Amplification for Real-Valued Functions.
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 2025-07-05 02:30 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 and maintained by:
the dblp computer science bibliography is funded and supported by:
