On the public citation graph

P = BPP if E requires exponential circuits

https://doi.org/10.1145/258533.258590
0 signed · 491 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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-61440-0_142openalex-snapshot
Hitting sets derandomize BPP
inferredcites →https://doi.org/10.1007/bf01275486openalex-snapshot
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
inferredcites →https://doi.org/10.1007/bf01375474openalex-snapshot
Pseudorandom bits for constant depth circuits
inferredcites →https://doi.org/10.1007/bf02579166openalex-snapshot
Eigenvalues and expanders
inferredcites →https://doi.org/10.1007/bf02579323openalex-snapshot
One way functions and pseudorandom generators
inferredcites →https://doi.org/10.1016/0885-064x(89)90015-0openalex-snapshot
On the power of two-point based sampling
inferredcites →https://doi.org/10.1016/s0022-0000(05)80043-1openalex-snapshot
Hardness vs randomness
inferredcites →https://doi.org/10.1090/dimacs/002/13openalex-snapshot
New directions in testing
inferredcites →https://doi.org/10.1109/fscs.1990.89550openalex-snapshot
Security preserving amplification of hardness
inferredcites →https://doi.org/10.1109/sct.1994.315814openalex-snapshot
A direct product theorem
inferredcites →https://doi.org/10.1109/sfcs.1982.95openalex-snapshot
Theory and application of trapdoor functions
inferredcites →https://doi.org/10.1109/sfcs.1989.63449openalex-snapshot
Dispersers, deterministic amplification, and weak random sources
inferredcites →https://doi.org/10.1109/sfcs.1989.63486openalex-snapshot
How to recycle random bits
inferredcites →https://doi.org/10.1109/sfcs.1994.365683openalex-snapshot
Products and help bits in decision trees
inferredcites →https://doi.org/10.1109/sfcs.1995.492584openalex-snapshot
Hard-core distributions for somewhat hard problems
inferredcites →https://doi.org/10.1137/0213053openalex-snapshot
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
inferredcites →https://doi.org/10.1145/225058.225181openalex-snapshot
A parallel repetition theorem
inferredcites →https://doi.org/10.1145/258533.258620openalex-snapshot
Direct product results and the GCD problem, in old and new communication models
inferredcites →https://doi.org/10.1145/28395.28410openalex-snapshot
Deterministic simulation in LOGSPACE
inferredcites →https://doi.org/10.1145/73007.73010openalex-snapshot
A hard-core predicate for all one-way functions
inferredcites →https://doi.org/10.1145/800061.808762openalex-snapshot
A complexity theoretic approach to randomness

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.5281/zenodo.17343522zenodo-depositor-declared
Deterministic Framework toward P = NP: A Polynomial-Time Uniqueness Test and Explicit Linear Isolation Scheme
inferred← citeshttps://doi.org/10.1002/9780470050118.ecse542openalex-snapshot
Computational Complexity Theory
inferred← citeshttps://doi.org/10.1002/jcd.21809openalex-snapshot
The combinatorial game N ofil played on Steiner triple systems
inferred← citeshttps://doi.org/10.1002/rsa.20498openalex-snapshot
A combination of testability and decodability by tensor products
inferred← citeshttps://doi.org/10.1006/jcss.1999.1646openalex-snapshot
Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds
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.2002.1824openalex-snapshot
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors
inferred← citeshttps://doi.org/10.1007/11523468_10openalex-snapshot
Simple Extractors via Constructions of Cryptographic Pseudo-random Generators
inferred← citeshttps://doi.org/10.1007/11533719_35openalex-snapshot
A Note on Zero Error Algorithms Having Oracle Access to One NP Query
inferred← citeshttps://doi.org/10.1007/11537311_37openalex-snapshot
Relations Between Average-Case and Worst-Case Complexity
inferred← citeshttps://doi.org/10.1007/11538462_39openalex-snapshot
Reconstructive Dispersers and Hitting Set Generators
inferred← citeshttps://doi.org/10.1007/11590156_2openalex-snapshot
Computational Complexity Since 1980
inferred← citeshttps://doi.org/10.1007/11590156_6openalex-snapshot
Proving Lower Bounds Via Pseudo-random Generators
inferred← citeshttps://doi.org/10.1007/11682462_52openalex-snapshot
Hardness Amplification Via Space-Efficient Direct Products
inferred← citeshttps://doi.org/10.1007/11753728_1openalex-snapshot
Non-black-box Techniques in Cryptography
inferred← citeshttps://doi.org/10.1007/11821069_41openalex-snapshot
Dimension Characterizations of Complexity Classes
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/11830924_37openalex-snapshot
Randomness-Efficient Sampling Within NC 1
inferred← citeshttps://doi.org/10.1007/11944836_12openalex-snapshot
On Obtaining Pseudorandomness from Error-Correcting Codes
inferred← citeshttps://doi.org/10.1007/3-540-32743-6_8openalex-snapshot
Von der Turingmaschine zum Quantencomputer — ein Gang durch die Geschichte der Komplexitätstheorie
inferred← citeshttps://doi.org/10.1007/3-540-36494-3_20openalex-snapshot
Some Results on Derandomization
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-44666-4_4openalex-snapshot
Error-Correcting Codes and Pseudorandom Projections
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-45022-x_58openalex-snapshot
Pseudorandomness
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-45322-9_4openalex-snapshot
Randomized Branching Programs
inferred← citeshttps://doi.org/10.1007/3-540-45726-7_16openalex-snapshot
A Probabilistic-Time Hierarchy Theorem for “Slightly Non-uniform” Algorithms
inferred← citeshttps://doi.org/10.1007/3-540-45726-7_17openalex-snapshot
Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good
inferred← citeshttps://doi.org/10.1007/3-540-48523-6_15openalex-snapshot
Small Pseudo-Random Sets Yield Hard Functions: New Tight Explicit Lower Bounds for Branching Programs
inferred← citeshttps://doi.org/10.1007/3-540-63165-8_175openalex-snapshot
Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs
inferred← citeshttps://doi.org/10.1007/978-1-4939-0748-9openalex-snapshot
The Compressed Word Problem for Groups
inferred← citeshttps://doi.org/10.1007/978-1-4939-0748-9_1openalex-snapshot
Preliminaries from Theoretical Computer Science
inferred← citeshttps://doi.org/10.1007/978-3-030-03807-6_16openalex-snapshot
Injective Trapdoor Functions via Derandomization: How Strong is Rudich’s Black-Box Barrier?
inferred← citeshttps://doi.org/10.1007/978-3-030-10801-4_15openalex-snapshot
Probabilistic Parameterized Polynomial Time
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-50026-9_15openalex-snapshot
Randomized and Symmetric Catalytic Computation
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-030-90456-2_13openalex-snapshot
Simple and Efficient Batch Verification Techniques for Verifiable Delay Functions
inferred← citeshttps://doi.org/10.1007/978-3-031-15802-5_6openalex-snapshot
(Nondeterministic) Hardness vs. Non-malleability
inferred← citeshttps://doi.org/10.1007/978-3-031-30545-0_2openalex-snapshot
Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality
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-58737-5_14openalex-snapshot
A Direct PRF Construction from Kolmogorov Complexity
inferred← citeshttps://doi.org/10.1007/978-3-031-58737-5_2openalex-snapshot
Non-malleable Codes with Optimal Rate for Poly-Size Circuits
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-032-01855-7_19openalex-snapshot
Uniform Black-Box Separations via Non-malleable Extractors
inferred← citeshttps://doi.org/10.1007/978-3-032-01855-7_20openalex-snapshot
Hardness Along the Boundary: Towards One-Way Functions from the Worst-Case Hardness of Time-Bounded Kolmogorov Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-05446-9_2openalex-snapshot
Investigations Concerning the Structure of Complete Sets
inferred← citeshttps://doi.org/10.1007/978-3-319-17142-5_8openalex-snapshot
Some New Consequences of the Hypothesis That P Has Fixed Polynomial-Size Circuits
inferred← citeshttps://doi.org/10.1007/978-3-319-21398-9_19openalex-snapshot
Evaluating Matrix Circuits
inferred← citeshttps://doi.org/10.1007/978-3-319-21398-9_39openalex-snapshot
Entropy of Weight Distributions of Small-Bias Spaces and Pseudobinomiality
inferred← citeshttps://doi.org/10.1007/978-3-319-32162-2_1openalex-snapshot
$$P\mathop{ =}\limits^{?}NP$$
inferred← citeshttps://doi.org/10.1007/978-3-319-56614-6_20openalex-snapshot
A Note on Perfect Correctness by Derandomization
inferred← citeshttps://doi.org/10.1007/978-3-319-58747-9_6openalex-snapshot
Can We Locally Compute Sparse Connected Subgraphs?
inferred← citeshttps://doi.org/10.1007/978-3-319-78381-9_9openalex-snapshot
Random Oracles and Non-uniformity
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-319-96878-0_5openalex-snapshot
Pseudorandom Quantum States
inferred← citeshttps://doi.org/10.1007/978-3-322-84823-9_19openalex-snapshot
Komplexitätstheoretische Ergebnisse für Randomisierte Branchingprogramme
inferred← citeshttps://doi.org/10.1007/978-3-540-24638-1_7openalex-snapshot
On the Possibility of One-Message Weak Zero-Knowledge
inferred← citeshttps://doi.org/10.1007/978-3-540-30538-5_28openalex-snapshot
Hardness Hypotheses, Derandomization, and Circuit Complexity
inferred← citeshttps://doi.org/10.1007/978-3-540-45077-1_31openalex-snapshot
Baire’s Categories on Small Complexity Classes
inferred← citeshttps://doi.org/10.1007/978-3-540-45146-4_18openalex-snapshot
Derandomization in Cryptography
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-48413-4_14openalex-snapshot
Improved Derandomization of BPP Using a Hitting Set Generator
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-74143-5_28openalex-snapshot
Chernoff-Type Direct Product Theorems
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-85238-4_18openalex-snapshot
Arthur and Merlin as Oracles
inferred← citeshttps://doi.org/10.1007/978-3-642-00457-5_8openalex-snapshot
Proofs of Retrievability via Hardness Amplification
inferred← citeshttps://doi.org/10.1007/978-3-642-00457-5_9openalex-snapshot
Security Amplification for Interactive Cryptographic Primitives
inferred← citeshttps://doi.org/10.1007/978-3-642-03356-8_10openalex-snapshot
On the Composition of Public-Coin Zero-Knowledge Protocols
inferred← citeshttps://doi.org/10.1007/978-3-642-03685-9_35openalex-snapshot
Extractors Using Hardness Amplification
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_41openalex-snapshot
The Complexity of Explicit Constructions
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-15205-4_23openalex-snapshot
Randomisation and Derandomisation in Descriptive Complexity Theory
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_46openalex-snapshot
Constructive Proofs of Concentration Bounds
inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_26openalex-snapshot
Some Recent Results on Local Testing of Sparse Linear Codes
inferred← citeshttps://doi.org/10.1007/978-3-642-19571-6_2openalex-snapshot
General Hardness Amplification of Predicates and Puzzles
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_48openalex-snapshot
Robust Simulations and Significant Separations
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_49openalex-snapshot
A PCP Characterization of AM
inferred← citeshttps://doi.org/10.1007/978-3-642-22670-0_20openalex-snapshot
In a World of P=BPP
inferred← citeshttps://doi.org/10.1007/978-3-642-22670-0_23openalex-snapshot
On Yao’s XOR-Lemma
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-22670-0_8openalex-snapshot
Simplified Derandomization of BPP Using a Hitting Set Generator
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-28914-9_22openalex-snapshot
Computational Extractors and Pseudorandomness
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_36openalex-snapshot
Optimal Hitting Sets for Combinatorial Shapes
inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_42openalex-snapshot
An Explicit VC-Theorem for Low-Degree Polynomials
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-38236-9_19openalex-snapshot
On Efficient Constructions of Short Lists Containing Mostly Ramsey Graphs
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-40273-9_9openalex-snapshot
Computing (and Life) Is All about Tradeoffs
inferred← citeshttps://doi.org/10.1007/978-3-642-40313-2_23openalex-snapshot
Learning Reductions to Sparse Sets
inferred← citeshttps://doi.org/10.1007/978-3-642-40313-2_48openalex-snapshot
Length-Increasing Reductions for PSPACE-Completeness
inferred← citeshttps://doi.org/10.1007/978-3-642-40328-6_37openalex-snapshot
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
inferred← citeshttps://doi.org/10.1007/978-3-662-12521-2openalex-snapshot
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
inferred← citeshttps://doi.org/10.1007/978-3-662-44465-8_30openalex-snapshot
On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity
inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_37openalex-snapshot
Parallel Identity Testing for Skew Circuits with Big Powers and Applications
inferred← citeshttps://doi.org/10.1007/978-3-662-48971-0_18openalex-snapshot
Heuristic Time Hierarchies via Hierarchies for Sampling Distributions
inferred← citeshttps://doi.org/10.1007/b104335openalex-snapshot
List Decoding of Error-Correcting Codes
inferred← citeshttps://doi.org/10.1007/bfb0055054openalex-snapshot
Do probabilistic algorithms outperform deterministic ones?
inferred← citeshttps://doi.org/10.1007/bfb0058034openalex-snapshot
On resource-bounded measure and pseudorandomness
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-0175-xopenalex-snapshot
Towards proving strong direct product theorems
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-005-0198-6openalex-snapshot
Compression of Samplable Sources
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-0232-yopenalex-snapshot
Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword
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-007-0238-5openalex-snapshot
Randomness-Efficient Sampling within NC1
inferred← citeshttps://doi.org/10.1007/s00037-008-0243-3openalex-snapshot
Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time
inferred← citeshttps://doi.org/10.1007/s00037-010-0291-3openalex-snapshot
Are PCPs Inherent in Efficient Arguments?
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-012-0043-7openalex-snapshot
Improved direct product theorems for randomized query complexity
inferred← citeshttps://doi.org/10.1007/s00037-013-0071-yopenalex-snapshot
Derandomized Parallel Repetition Theorems for Free Games
inferred← citeshttps://doi.org/10.1007/s00037-013-0076-6openalex-snapshot
Randomness Buys Depth for Approximate Counting
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-015-0100-0openalex-snapshot
Mining Circuit Lower Bound Proofs for Meta-Algorithms
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-016-0150-yopenalex-snapshot
On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace
inferred← citeshttps://doi.org/10.1007/s00037-019-00179-2openalex-snapshot
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials
inferred← citeshttps://doi.org/10.1007/s00037-020-00203-wopenalex-snapshot
Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels
inferred← citeshttps://doi.org/10.1007/s00037-023-00238-9openalex-snapshot
Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?
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/s00145-021-09405-zopenalex-snapshot
Injective Trapdoor Functions via Derandomization: How Strong is Rudich’s Black-Box Barrier?
inferred← citeshttps://doi.org/10.1007/s00145-022-09428-0openalex-snapshot
A Note on Perfect Correctness by Derandomization
inferred← citeshttps://doi.org/10.1007/s00224-004-1194-yopenalex-snapshot
Some Results on Derandomization
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-011-9368-xopenalex-snapshot
The Complexity of Explicit Constructions
inferred← citeshttps://doi.org/10.1007/s00224-014-9535-yopenalex-snapshot
On Optimal Language Compression for Sets in PSPACE/poly
inferred← citeshttps://doi.org/10.1007/s00224-016-9680-6openalex-snapshot
Small-Bias is Not Enough to Hit Read-Once CNF
inferred← citeshttps://doi.org/10.1007/s00224-017-9784-7openalex-snapshot
Catalytic Space: Non-determinism and Hierarchy
inferred← citeshttps://doi.org/10.1007/s00224-017-9808-3openalex-snapshot
Knapsack in Graph Groups
inferred← citeshttps://doi.org/10.1007/s00224-018-9872-3openalex-snapshot
Verification of Quantum Computation: An Overview of Existing Approaches
inferred← citeshttps://doi.org/10.1007/s00224-023-10119-xopenalex-snapshot
Effective Guessing Has Unlikely Consequences
inferred← citeshttps://doi.org/10.1007/s00453-008-9266-zopenalex-snapshot
Reconstructive Dispersers and Hitting Set Generators
inferred← citeshttps://doi.org/10.1007/s00453-017-0343-zopenalex-snapshot
Evaluation of Circuits Over Nilpotent and Polycyclic Groups
inferred← citeshttps://doi.org/10.1007/s00493-003-0025-0openalex-snapshot
Improved Low-Degree Testing and its Applications
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.1007/s10878-006-7130-0openalex-snapshot
On zero error algorithms having oracle access to one query
inferred← citeshttps://doi.org/10.1007/s11047-006-9016-6openalex-snapshot
A broader view on the limitations of information processing and communication by nature
inferred← citeshttps://doi.org/10.1016/j.apal.2007.09.003openalex-snapshot
The parameterized complexity of maximality and minimality problems
inferred← citeshttps://doi.org/10.1016/j.dam.2007.06.023openalex-snapshot
Computation of best possible low degree expanders
inferred← citeshttps://doi.org/10.1016/j.ic.2009.02.002openalex-snapshot
A zero-one law for RP and derandomization of AM if NP is not small
inferred← citeshttps://doi.org/10.1016/j.ic.2017.07.002openalex-snapshot
Robust simulations and significant separations
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.2005.06.010openalex-snapshot
Lower bounds for non-black-box zero knowledge
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.007openalex-snapshot
Infeasibility of instance compression and succinct PCPs for NP
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.2004.02.029openalex-snapshot
The size of SPP
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.10.009openalex-snapshot
Improved hardness amplification in NP
inferred← citeshttps://doi.org/10.1016/j.tcs.2009.10.020openalex-snapshot
Simple extractors via constructions of cryptographic pseudo-random generators
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.02.005openalex-snapshot
Metric structures and probabilistic computation
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/s0168-0072(00)00017-8openalex-snapshot
Interactive and probabilistic proof-checking
inferred← citeshttps://doi.org/10.1016/s0304-0208(04)80009-4openalex-snapshot
Bibliography
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00568-6openalex-snapshot
Approximation of boolean functions by combinatorial rectangles
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00643-6openalex-snapshot
Almost k-wise independence and hard Boolean functions
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00810-1openalex-snapshot
Uniformly hard languages
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00024-9openalex-snapshot
Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
inferred← citeshttps://doi.org/10.1017/cbo9780511979309.018openalex-snapshot
Interactive proofs, circuit lower bounds, and more
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.1038/d41586-021-00694-9openalex-snapshot
Abel Prize celebrates union of mathematics and computer science
inferred← citeshttps://doi.org/10.1038/d41586-024-01055-yopenalex-snapshot
Randomness in computation wins computer-science ‘Nobel’
inferred← citeshttps://doi.org/10.1073/pnas.1901272116openalex-snapshot
Bootstrapping variables in algebraic circuits
inferred← citeshttps://doi.org/10.1090/ulect/055openalex-snapshot
A Primer on Pseudorandom Generators
inferred← citeshttps://doi.org/10.1093/acprof:oso/9780199233212.001.0001openalex-snapshot
The Nature of Computation
inferred← citeshttps://doi.org/10.1093/acprof:oso/9780199233212.002.0003openalex-snapshot
Copyright Page
inferred← citeshttps://doi.org/10.1093/acprof:oso/9780199233212.002.0004openalex-snapshot
Dedication
inferred← citeshttps://doi.org/10.1093/acprof:oso/9780199233212.002.0006openalex-snapshot
Figure Credits
inferred← citeshttps://doi.org/10.1093/acprof:oso/9780199233212.002.0007openalex-snapshot
Preface
inferred← citeshttps://doi.org/10.1093/acprof:oso/9780199233212.003.0001openalex-snapshot
Prologue
inferred← citeshttps://doi.org/10.1093/acprof:oso/9780199233212.003.0002openalex-snapshot
The Basics
inferred← citeshttps://doi.org/10.1093/acprof:oso/9780199233212.003.0003openalex-snapshot
Insights and Algorithms
inferred← citeshttps://doi.org/10.1093/acprof:oso/9780199233212.003.0004openalex-snapshot
Needles in a Haystack: the Class NP
inferred← citeshttps://doi.org/10.1093/acprof:oso/9780199233212.003.0005openalex-snapshot
Who is the Hardest One of All? NP-Completeness
showing the first 200 of 470
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.