On the public citation graph
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
0 signed · 310 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/3-540-52282-4_30openalex-snapshot
Hiding instances in multioracle queries
inferredcites →https://doi.org/10.1007/bf01200056openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf01200057openalex-snapshot
Arithmetization: A new method in structural complexity theory
inferredcites →https://doi.org/10.1007/bf01200430openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf02579323openalex-snapshot
One way functions and pseudorandom generators
inferredcites →https://doi.org/10.1016/0022-0000(88)90028-1openalex-snapshot
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
inferredcites →https://doi.org/10.1016/s0019-9958(85)80004-8openalex-snapshot
Sparse sets in NP-P: EXPTIME versus NEXPTIME
inferredcites →https://doi.org/10.1016/s0019-9958(86)80012-2openalex-snapshot
On relativized exponential and probabilistic complexity classes
inferredcites →https://doi.org/10.1109/sfcs.1978.37openalex-snapshot
Two theorems on random polynomial time
inferredcites →https://doi.org/10.1109/sfcs.1982.45openalex-snapshot
Theory and application of trapdoor functions
inferredcites →https://doi.org/10.1109/sfcs.1982.95openalex-snapshot
Theory and application of trapdoor functions
inferredcites →https://doi.org/10.1109/sfcs.1988.21917openalex-snapshot
On the existence of pseudorandom generators
inferredcites →https://doi.org/10.1137/0210008openalex-snapshot
Relative to a Random Oracle A , ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
inferredcites →https://doi.org/10.1137/0213053openalex-snapshot
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
inferredcites →https://doi.org/10.1137/0218012openalex-snapshot
The Knowledge Complexity of Interactive Proof Systems
inferredcites →https://doi.org/10.1145/100216.100225openalex-snapshot
Self-testing/correcting with applications to numerical problems
inferredcites →https://doi.org/10.1145/100216.100270openalex-snapshot
Pseudo-random generators under uniform assumptions
inferredcites →https://doi.org/10.1145/146585.146605openalex-snapshot
Algebraic methods for interactive proof systems
inferredcites →https://doi.org/10.1145/22145.22192openalex-snapshot
Trading group theory for randomness
inferredcites →https://doi.org/10.1145/62212.62223openalex-snapshot
Multi-prover interactive proofs: how to remove intractability
inferredcites →https://doi.org/10.1145/73007.73009openalex-snapshot
Pseudo-random generation from one-way functions
inferredcites →https://doi.org/10.1145/73007.73010openalex-snapshot
A hard-core predicate for all one-way functions
inferredcites →https://doi.org/10.1145/73007.73015openalex-snapshot
Designing programs that check their work
inferredcites →https://doi.org/10.1145/800141.804678openalex-snapshot
Some connections between nonuniform and uniform complexity classes
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/rsa.20069openalex-snapshot
Lower bounds for adaptive locally decodable codes
inferred← citeshttps://doi.org/10.1002/rsa.20498openalex-snapshot
A combination of testability and decodability by tensor products
inferred← citeshttps://doi.org/10.1002/rsa.21031openalex-snapshot
Erasures versus errors in local decoding and property testing
inferred← citeshttps://doi.org/10.1006/jcss.2000.1730openalex-snapshot
Pseudorandom Generators without the XOR Lemma
inferred← citeshttps://doi.org/10.1006/jcss.2001.1763openalex-snapshot
Easiness Assumptions and Hardness Tests: Trading Time for Zero Error
inferred← citeshttps://doi.org/10.1006/jcss.2001.1780openalex-snapshot
Randomness vs Time: Derandomization under a Uniform Assumption
inferred← citeshttps://doi.org/10.1006/jcss.2002.1835openalex-snapshot
New Lowness Results for ZPPNP and Other Complexity Classes
inferred← citeshttps://doi.org/10.1007/11494645_61openalex-snapshot
Arthur-Merlin Games and the Problem of Isomorphism Testing
inferred← citeshttps://doi.org/10.1007/11537311_37openalex-snapshot
Relations Between Average-Case and Worst-Case Complexity
inferred← citeshttps://doi.org/10.1007/11590156_2openalex-snapshot
Computational Complexity Since 1980
inferred← citeshttps://doi.org/10.1007/11682462_52openalex-snapshot
Hardness Amplification Via Space-Efficient Direct Products
inferred← citeshttps://doi.org/10.1007/11776420_27openalex-snapshot
Efficient Learning Algorithms Yield Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/11830924_36openalex-snapshot
Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
inferred← citeshttps://doi.org/10.1007/11944836_12openalex-snapshot
On Obtaining Pseudorandomness from Error-Correcting Codes
inferred← citeshttps://doi.org/10.1007/3-540-40996-3_26openalex-snapshot
Derandomizing Arthur-Merlin Games under Uniform Assumptions
inferred← citeshttps://doi.org/10.1007/3-540-44666-4_28openalex-snapshot
On the Derandomization of Constant Depth Circuits
inferred← citeshttps://doi.org/10.1007/3-540-44849-7_26openalex-snapshot
Nearly Bounded Error Probabilistic Sets
inferred← citeshttps://doi.org/10.1007/3-540-44929-9_3openalex-snapshot
List Decoding: Algorithms and Applications
inferred← citeshttps://doi.org/10.1007/3-540-45294-x_1openalex-snapshot
When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity
inferred← citeshttps://doi.org/10.1007/3-540-45294-x_6openalex-snapshot
Hard Sets and Pseudo-random Generators for Constant Depth Circuits
inferred← citeshttps://doi.org/10.1007/3-540-46541-3_36openalex-snapshot
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results
inferred← citeshttps://doi.org/10.1007/3-540-48686-0_21openalex-snapshot
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy
inferred← citeshttps://doi.org/10.1007/3-540-62034-6_33openalex-snapshot
Circuit complexity before the dawn of the new millennium
inferred← citeshttps://doi.org/10.1007/3-540-63165-8_176openalex-snapshot
Results on resource-bounded measure
inferred← citeshttps://doi.org/10.1007/3-540-63248-4_14openalex-snapshot
Using hard problems to derandomize algorithms: An incomplete survey
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_691openalex-snapshot
Large-Treewidth Graph Decompositions
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_708openalex-snapshot
Locally Decodable Codes
inferred← citeshttps://doi.org/10.1007/978-3-030-17653-2_17openalex-snapshot
Non-Malleable Codes Against Bounded Polynomial Time Tampering
inferred← citeshttps://doi.org/10.1007/978-3-030-43662-9_15openalex-snapshot
Worst-Case to Average-Case Reductions for Subclasses of P
inferred← citeshttps://doi.org/10.1007/978-3-030-90453-1_15openalex-snapshot
On Derandomizing Yao’s Weak-to-Strong OWF Construction
inferred← citeshttps://doi.org/10.1007/978-3-031-36978-0_9openalex-snapshot
Some Games on Turing Machines and Power from Random Strings
inferred← citeshttps://doi.org/10.1007/978-3-031-78011-0_9openalex-snapshot
One-Way Functions and pKt Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-91908-9_2openalex-snapshot
Some Estimated Likelihoods for Computational Complexity
inferred← citeshttps://doi.org/10.1007/978-3-540-24587-2_21openalex-snapshot
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
inferred← citeshttps://doi.org/10.1007/978-3-540-45198-3_18openalex-snapshot
Computational Analogues of Entropy
inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_18openalex-snapshot
On the Complexity of Hard-Core Set Constructions
inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_35openalex-snapshot
Private Locally Decodable Codes
inferred← citeshttps://doi.org/10.1007/978-3-540-74143-5_28openalex-snapshot
Chernoff-Type Direct Product Theorems
inferred← citeshttps://doi.org/10.1007/978-3-540-74208-1_23openalex-snapshot
On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR
inferred← citeshttps://doi.org/10.1007/978-3-540-74208-1_41openalex-snapshot
Worst-Case to Average-Case Reductions Revisited
inferred← citeshttps://doi.org/10.1007/978-3-540-74240-1_35openalex-snapshot
Impossibility Results on Weakly Black-Box Hardness Amplification
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_37openalex-snapshot
Limitations of Hardness vs. Randomness under Uniform Reductions
inferred← citeshttps://doi.org/10.1007/978-3-642-10631-6_110openalex-snapshot
General Pseudo-random Generators from Weaker Models of Computation
inferred← citeshttps://doi.org/10.1007/978-3-642-13962-8_1openalex-snapshot
Avoiding Simplicity Is Complex
inferred← citeshttps://doi.org/10.1007/978-3-642-13962-8_42openalex-snapshot
Kolmogorov Complexity Cores
inferred← citeshttps://doi.org/10.1007/978-3-642-14031-0_4openalex-snapshot
On the Hardness against Constant-Depth Linear-Size Circuits
inferred← citeshttps://doi.org/10.1007/978-3-642-14358-8openalex-snapshot
Locally Decodable Codes and Private Information Retrieval Schemes
inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_29openalex-snapshot
Uniform Derandomization from Pathetic Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_56openalex-snapshot
Relativized Worlds without Worst-Case to Average-Case Reductions for NP
inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_29openalex-snapshot
Local Property Reconstruction and Monotonicity
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_25openalex-snapshot
Limits on the Computational Power of Random Strings
inferred← citeshttps://doi.org/10.1007/978-3-642-22670-0_6openalex-snapshot
Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_32openalex-snapshot
Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_708-1openalex-snapshot
Locally Decodable Codes
inferred← citeshttps://doi.org/10.1007/978-3-642-32241-9_36openalex-snapshot
On TC0 Lower Bounds for the Permanent
inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_55openalex-snapshot
A Combination of Testability and Decodability by Tensor Products
inferred← citeshttps://doi.org/10.1007/978-3-642-38233-8_16openalex-snapshot
Succinct Permanent Is NEXP-Hard with Many Hard Instances
inferred← citeshttps://doi.org/10.1007/978-3-642-38536-0_15openalex-snapshot
Towards NEXP versus BPP?
inferred← citeshttps://doi.org/10.1007/978-3-642-55220-5_35openalex-snapshot
Distributed Point Functions and Their Applications
inferred← citeshttps://doi.org/10.1007/b104335openalex-snapshot
List Decoding of Error-Correcting Codes
inferred← citeshttps://doi.org/10.1007/bfb0023469openalex-snapshot
A downward translation in the polynomial hierarchy
inferred← citeshttps://doi.org/10.1007/bfb0028558openalex-snapshot
A generalization of resource-bounded measure, with an application (Extended abstract)
inferred← citeshttps://doi.org/10.1007/bfb0055799openalex-snapshot
Average-case intractability vs. worst-case intractability
inferred← citeshttps://doi.org/10.1007/s00037-001-8196-9openalex-snapshot
Derandomizing Arthur--Merlin games under uniform assumptions
inferred← citeshttps://doi.org/10.1007/s00037-003-0178-7openalex-snapshot
Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
inferred← citeshttps://doi.org/10.1007/s00037-004-0182-6openalex-snapshot
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/s00037-004-0187-1openalex-snapshot
The complexity of constructing pseudorandom generators from hard functions
inferred← citeshttps://doi.org/10.1007/s00037-005-0197-7openalex-snapshot
Derandomizing Arthur–Merlin Games using Hitting Sets
inferred← citeshttps://doi.org/10.1007/s00037-007-0218-9openalex-snapshot
Pseudorandomness for Approximate Counting and Sampling
inferred← citeshttps://doi.org/10.1007/s00037-007-0233-xopenalex-snapshot
Pseudorandomness and Average-Case Complexity Via Uniform Reductions
inferred← citeshttps://doi.org/10.1007/s00037-007-0235-8openalex-snapshot
If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances
inferred← citeshttps://doi.org/10.1007/s00037-011-0003-7openalex-snapshot
Complexity of Hard-Core Set Proofs
inferred← citeshttps://doi.org/10.1007/s00037-011-0006-4openalex-snapshot
Weak Derandomization of Weak Algorithms: Explicit Versions of Yao’s Lemma
inferred← citeshttps://doi.org/10.1007/s00037-011-0010-8openalex-snapshot
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds
inferred← citeshttps://doi.org/10.1007/s00037-011-0019-zopenalex-snapshot
Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/s00037-012-0036-6openalex-snapshot
Pseudorandom Generators for Combinatorial Checkerboards
inferred← citeshttps://doi.org/10.1007/s00037-014-0095-yopenalex-snapshot
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
inferred← citeshttps://doi.org/10.1007/s00037-016-0128-9openalex-snapshot
Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions
inferred← citeshttps://doi.org/10.1007/s00037-016-0134-yopenalex-snapshot
Fourier Concentration from Shrinkage
inferred← citeshttps://doi.org/10.1007/s00037-023-00241-0openalex-snapshot
The Power of Natural Properties as Oracles
inferred← citeshttps://doi.org/10.1007/s00037-024-00260-5openalex-snapshot
On the Structure of Learnability beyond P/poly
inferred← citeshttps://doi.org/10.1007/s00037-025-00279-2openalex-snapshot
Instance-Wise Hardness and Refutation versus Derandomization for Arthur-Merlin Protocols
inferred← citeshttps://doi.org/10.1007/s00145-008-9029-7openalex-snapshot
Chernoff-Type Direct Product Theorems
inferred← citeshttps://doi.org/10.1007/s00224-007-9071-0openalex-snapshot
Relations between Average-Case and Worst-Case Complexity
inferred← citeshttps://doi.org/10.1007/s00224-011-9334-7openalex-snapshot
Avoiding Simplicity is Complex
inferred← citeshttps://doi.org/10.1007/s00224-011-9365-0openalex-snapshot
Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses
inferred← citeshttps://doi.org/10.1007/s00224-022-10083-yopenalex-snapshot
Nonuniform Reductions and NP-Completeness
inferred← citeshttps://doi.org/10.1007/s00453-008-9272-1openalex-snapshot
On Locally Decodable Codes, Self-Correctable Codes, and t-Private PIR
inferred← citeshttps://doi.org/10.1007/s00493-006-0036-8openalex-snapshot
Reducing The Seed Length In The Nisan-Wigderson Generator*
inferred← citeshttps://doi.org/10.1016/b978-0-444-51624-4.50011-3openalex-snapshot
Computational Complexity
inferred← citeshttps://doi.org/10.1016/j.ic.2011.09.008openalex-snapshot
Limits on the computational power of random strings
inferred← citeshttps://doi.org/10.1016/j.ipl.2019.105841openalex-snapshot
Proving that prBPP = prP is as hard as proving that “almost NP” is not contained in P/poly
inferred← citeshttps://doi.org/10.1016/j.jcss.2004.01.001openalex-snapshot
Hardness amplification within NP
inferred← citeshttps://doi.org/10.1016/j.jcss.2004.04.007openalex-snapshot
Exponential lower bound for 2-query locally decodable codes via a quantum argument
inferred← citeshttps://doi.org/10.1016/j.jcss.2008.07.006openalex-snapshot
Efficient learning algorithms yield circuit lower bounds
inferred← citeshttps://doi.org/10.1016/j.jcss.2010.06.004openalex-snapshot
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
inferred← citeshttps://doi.org/10.1016/j.jcss.2010.06.008openalex-snapshot
Hardness amplification within NP against deterministic algorithms
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.04.038openalex-snapshot
Circuit lower bounds from learning-theoretic approaches
inferred← citeshttps://doi.org/10.1016/s0022-0000(02)00024-7openalex-snapshot
In search of an easy witness: exponential time vs. probabilistic polynomial time
inferred← citeshttps://doi.org/10.1016/s0022-0000(03)00046-1openalex-snapshot
Pseudo-random generators for all hardnesses
inferred← citeshttps://doi.org/10.1016/s0065-2458(09)01204-2openalex-snapshot
Chapter 4 A Status Report on the P Versus NP Question
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00810-1openalex-snapshot
Uniformly hard languages
inferred← citeshttps://doi.org/10.1017/cbo9781107338579.009openalex-snapshot
Turing and the development of computational complexity
inferred← citeshttps://doi.org/10.1023/a:1022949332276openalex-snapshot
Boosting and Hard-Core Set Construction
inferred← citeshttps://doi.org/10.1090/jams/864openalex-snapshot
Geometric complexity theory V: Efficient algorithms for Noether normalization
inferred← citeshttps://doi.org/10.1090/ulect/055openalex-snapshot
A Primer on Pseudorandom Generators
inferred← citeshttps://doi.org/10.1098/rsta.2011.0318openalex-snapshot
Uniform derandomization from pathetic lower bounds
inferred← citeshttps://doi.org/10.1109/ccc.1998.694603openalex-snapshot
On the resource bounded measure of P/poly
inferred← citeshttps://doi.org/10.1109/ccc.1998.694620openalex-snapshot
Resource bounded measure and learnability
inferred← citeshttps://doi.org/10.1109/ccc.1999.766263openalex-snapshot
De-randomizing BPP: the state of the art
inferred← citeshttps://doi.org/10.1109/ccc.2000.856746openalex-snapshot
Easiness assumptions and hardness tests: trading time for zero error
inferred← citeshttps://doi.org/10.1109/ccc.2001.933865openalex-snapshot
In search of an easy witness: exponential time vs. probabilistic polynomial time
inferred← citeshttps://doi.org/10.1109/ccc.2001.933869openalex-snapshot
Comparing notions of full derandomization
inferred← citeshttps://doi.org/10.1109/ccc.2002.1004348openalex-snapshot
Pseudorandomness and average-case complexity via uniform reductions
inferred← citeshttps://doi.org/10.1109/ccc.2002.1004354openalex-snapshot
Better lower bounds for locally decodable codes
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214408openalex-snapshot
Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214410openalex-snapshot
Hardness vs. randomness within alternating time
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214421openalex-snapshot
Derandomization and distinguishing complexity
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214427openalex-snapshot
Holographic proofs and derandomization
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313808openalex-snapshot
Solvable group isomorphism is (almost) in NP ∩ coNP
inferred← citeshttps://doi.org/10.1109/ccc.2004.33openalex-snapshot
Solvable Group Isomorphism is (almost) in NP CoNP
inferred← citeshttps://doi.org/10.1109/ccc.2005.11openalex-snapshot
If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances
inferred← citeshttps://doi.org/10.1109/ccc.2005.17openalex-snapshot
On the Complexity of Hardness Amplification
inferred← citeshttps://doi.org/10.1109/ccc.2005.25openalex-snapshot
Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates
inferred← citeshttps://doi.org/10.1109/ccc.2008.14openalex-snapshot
Noisy Interpolating Sets for Low Degree Polynomials
inferred← citeshttps://doi.org/10.1109/ccc.2008.17openalex-snapshot
Hardness Amplification within NP against Deterministic Algorithms
inferred← citeshttps://doi.org/10.1109/ccc.2009.21openalex-snapshot
Fixed-Polynomial Size Circuit Bounds
inferred← citeshttps://doi.org/10.1109/ccc.2009.27openalex-snapshot
Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma
inferred← citeshttps://doi.org/10.1109/ccc.2010.13openalex-snapshot
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds
inferred← citeshttps://doi.org/10.1109/ccc.2011.34openalex-snapshot
Relativized Separations of Worst-Case and Average-Case Complexities for NP
inferred← citeshttps://doi.org/10.1109/ccc.2011.36openalex-snapshot
Non-uniform ACC Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1109/ccc.2012.32openalex-snapshot
Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games
inferred← citeshttps://doi.org/10.1109/ccc.2013.18openalex-snapshot
Constructing Hard Functions Using Learning Algorithms
inferred← citeshttps://doi.org/10.1109/ccc.2014.33openalex-snapshot
Algorithms for Circuits and Circuits for Algorithms
inferred← citeshttps://doi.org/10.1109/ccc.2014.39openalex-snapshot
Fourier Concentration from Shrinkage
inferred← citeshttps://doi.org/10.1109/focs.2006.13openalex-snapshot
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification
inferred← citeshttps://doi.org/10.1109/focs.2012.15openalex-snapshot
Geometric Complexity Theory V: Equivalence between Blackbox Derandomization of Polynomial Identity Testing and Derandomization of Noether's Normalization Lemma
inferred← citeshttps://doi.org/10.1109/focs.2014.20openalex-snapshot
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing
inferred← citeshttps://doi.org/10.1109/focs.2018.00017openalex-snapshot
Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems
inferred← citeshttps://doi.org/10.1109/focs.2018.00032openalex-snapshot
Non-Black-Box Worst-Case to Average-Case Reductions within NP
inferred← citeshttps://doi.org/10.1109/focs.2019.00065openalex-snapshot
Stoquastic PCP vs. Randomness
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00010openalex-snapshot
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00119openalex-snapshot
Is it Easier to Prove Theorems that are Guaranteed to be True?
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00021openalex-snapshot
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00058openalex-snapshot
Hardness Self-Amplification from Feasible Hard-Core Sets
inferred← citeshttps://doi.org/10.1109/istcs.1995.377029openalex-snapshot
Computational pseudo-randomness
inferred← citeshttps://doi.org/10.1109/sfcs.1997.646115openalex-snapshot
Weak random sources, hitting sets, and BPP simulations
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743524openalex-snapshot
Randomness vs. time: de-randomization under a uniform assumption
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892063openalex-snapshot
Extracting randomness from samplable distributions
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959941openalex-snapshot
Simple extractors for all min-entropies and a new pseudo-random generator
inferred← citeshttps://doi.org/10.1109/sffcs.1999.814579openalex-snapshot
Derandomizing Arthur-Merlin games using hitting sets
inferred← citeshttps://doi.org/10.1109/sffcs.1999.814590openalex-snapshot
Near-optimal conversion of hardness into pseudo-randomness
inferred← citeshttps://doi.org/10.1109/sffcs.1999.814638openalex-snapshot
Boosting and hard-core sets
inferred← citeshttps://doi.org/10.1109/tit.2008.928988openalex-snapshot
On the Complexity of Hardness Amplification
inferred← citeshttps://doi.org/10.1109/tit.2021.3131992openalex-snapshot
Efficient List-Decoding With Constant Alphabet and List Sizes
inferred← citeshttps://doi.org/10.1109/tit.2024.3357703openalex-snapshot
Threshold Rates of Code Ensembles: Linear Is Best
inferred← citeshttps://doi.org/10.1109/tit.2024.3430842openalex-snapshot
Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery
inferred← citeshttps://doi.org/10.1137/050640941openalex-snapshot
Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
inferred← citeshttps://doi.org/10.1137/070683994openalex-snapshot
Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification
inferred← citeshttps://doi.org/10.1137/070698348openalex-snapshot
Low-End Uniform Hardness versus Randomness Tradeoffs for AM
inferred← citeshttps://doi.org/10.1137/080735096openalex-snapshot
Hardness Amplification Proofs Require Majority
inferred← citeshttps://doi.org/10.1137/1.9781611974782.141openalex-snapshot
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
inferred← citeshttps://doi.org/10.1137/10080703xopenalex-snapshot
Improving Exhaustive Search Implies Superpolynomial Lower Bounds
inferred← citeshttps://doi.org/10.1137/130938219openalex-snapshot
Natural Proofs versus Derandomization
inferred← citeshttps://doi.org/10.1137/17m116149xopenalex-snapshot
Local List Recovery of High-Rate Tensor Codes and Applications
inferred← citeshttps://doi.org/10.1137/18m1195887openalex-snapshot
Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
inferred← citeshttps://doi.org/10.1137/19m124705xopenalex-snapshot
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
inferred← citeshttps://doi.org/10.1137/22m1475491openalex-snapshot
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise
inferred← citeshttps://doi.org/10.1137/23m1608483openalex-snapshot
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
inferred← citeshttps://doi.org/10.1137/s0097539700389652openalex-snapshot
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
inferred← citeshttps://doi.org/10.1137/s0097539701389944openalex-snapshot
Pseudorandom Generators in Propositional Proof Complexity
inferred← citeshttps://doi.org/10.1137/s0097539703438629openalex-snapshot
Holographic Proofs and Derandomization
inferred← citeshttps://doi.org/10.1137/s0097539705447281openalex-snapshot
Using Nondeterminism to Amplify Hardness
inferred← citeshttps://doi.org/10.1137/s0097539793244708openalex-snapshot
A Pseudorandom Generator from any One-way Function
inferred← citeshttps://doi.org/10.1137/s0097539796306474openalex-snapshot
A Downward Collapse within the Polynomial Hierarchy
inferred← citeshttps://doi.org/10.1137/s0097539797325636openalex-snapshot
Weak Random Sources, Hitting Sets, and BPP Simulations
inferred← citeshttps://doi.org/10.1137/s0097539798343891openalex-snapshot
A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
inferred← citeshttps://doi.org/10.1142/9789812562494_0012openalex-snapshot
DERANDOMIZATION: A BRIEF OVERVIEW
inferred← citeshttps://doi.org/10.1142/9789812562494_0013openalex-snapshot
RECENT DEVELOPMENTS IN EXPLICIT CONSTRUCTIONS OF EXTRACTORS
inferred← citeshttps://doi.org/10.1142/9789814324359_0165openalex-snapshot
The Unified Theory of Pseudorandomness
inferred← citeshttps://doi.org/10.1142/s0129054105003819openalex-snapshot
NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
inferred← citeshttps://doi.org/10.1142/s1793830910000851openalex-snapshot
ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
inferred← citeshttps://doi.org/10.1145/1007352.1007389openalex-snapshot
Using nondeterminism to amplify hardness
inferred← citeshttps://doi.org/10.1145/1059513.1059516openalex-snapshot
Simple extractors for all min-entropies and a new pseudorandom generator
inferred← citeshttps://doi.org/10.1145/1132516.1132571openalex-snapshot
Can every randomized algorithm be derandomized?
inferred← citeshttps://doi.org/10.1145/1132516.1132615openalex-snapshot
On the randomness complexity of efficient sampling
inferred← citeshttps://doi.org/10.1145/1250790.1250854openalex-snapshot
Low-end uniform hardness vs. randomness tradeoffs for AM
inferred← citeshttps://doi.org/10.1145/1250790.1250855openalex-snapshot
Verifying and decoding in constant depth
showing the first 200 of 283 · page through all 283
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.