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.
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-06-30 20:37 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:
