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. - Igor Balla, Lianna Hambardzumyan, István Tomon:
Factorization norms and an inverse theorem for MaxCut. - Valentine Kabanets, Antonina Kolokolova:
Chain Rules for Time-Bounded Kolmogorov Complexity. - Noor Athamnah, Noga Ron-Zewi, Ron Rothblum:
Linear Prover IOPs in Log Star Rounds. - Tamer Mour, Alon Rosen, Ron Rothblum:
Tree PCPs. - Shuichi Hirahara, Mikito Nanashima:
Complexity-Theoretic Inductive Inference. - Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan:
Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications. - Shuichi Hirahara, Rahul Ilango, Bruno Loff:
Communication Complexity is NP-hard. - Rahul Ilango:
Godel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness. - Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan:
Searching for Falsified Clause in Random log{n}-CNFs is Hard for Randomized Communication. - Hadar Strauss:
On the Limits of Computationally Sound IPPs in the Isolated Model. - Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, Amit Sinhababu:
IPS Lower Bounds for Formulas and Sum of1 ROABPs. - Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff:
The Algebraic Cost of a Boolean Sum. - Mika Göös, Nathaniel Harms, Artur Riazanov:
Equality is Far Weaker Than Constant-Cost Communication. - Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett:
Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis. - Bruno Pasqualotto Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Monotone Circuit Complexity of Matching. - Rohit Gurjar, Kilian Rothmund, Thomas Thierauf:
2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs. - Oliver Korten, Rahul Santhanam:
How to Construct Random Strings. - Oded Goldreich, Guy N. Rothblum:
Location-Invariant Properties of Functions versus Properties of Distributions: United in Testing but Separated in Verification. - Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay:
Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth. - Justin Oh, Ronen Shaltiel:
Extractors for Samplable Distributions from the Two-Source Extractor Recipe. - Divesh Aggarwal, Pranjal Dutta, Saswata Mukherjee, Satyajeet Nagargoje, Maciej Obremski:
Efficient randomized strong 2-source non-malleable extractor for any linear min-entropy. - Dmitry Itsykson, Alexander Knop:
Supercritical Tradeoff Between Size and Depth for Resolution over Parities. - Uma Girish, Rocco A. Servedio:
Forrelation is Extremally Hard. - Farzan Byramji, Russell Impagliazzo:
Lower bounds for the Bit Pigeonhole Principle in Bounded-Depth Resolution over Parities. - John M. Hitchcock, Adewale Sekoni, Hadi Shafei:
Counting Martingales for Measure and Dimension in Complexity Classes. - Shuichi Hirahara, Naoto Ohsaka:
Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration. - Karthik Gajulapalli, Surendra Ghentiyala, Zeyong Li, Sidhant Saraogi:
Downward self-reducibility in the total function polynomial hierarchy. - Soumik Ghosh, Sathyawageeswar Subramanian, Wei Zhan:
Unconditional Pseudorandomness against Shallow Quantum Circuits. - Surendra Ghentiyala, Zeyong Li:
Hierarchies within TFNP: building blocks and collapses. - Marko Chalupa:
An AC0 Lower Bound for Random Satisfiable 3-CNF under Standard Random Restrictions.
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-09-13 21:31 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:
