On the public citation graph
Using nondeterminism to amplify hardness
0 signed · 59 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.1002/rsa.10097openalex-snapshot
On the noise sensitivity of monotone functions
inferredcites →https://doi.org/10.1006/jcss.2000.1730openalex-snapshot
Pseudorandom Generators without the XOR Lemma
inferredcites →https://doi.org/10.1006/jcss.2001.1780openalex-snapshot
Randomness vs Time: Derandomization under a Uniform Assumption
inferredcites →https://doi.org/10.1007/3-540-52282-4_30openalex-snapshot
Hiding instances in multioracle queries
inferredcites →https://doi.org/10.1007/978-3-540-27821-4_34openalex-snapshot
Fooling Parity Tests with Parity Gates
inferredcites →https://doi.org/10.1007/bf01200056openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf01200430openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf01262928openalex-snapshot
On the hardness of computing the permanent of random matrices
inferredcites →https://doi.org/10.1007/bf01275486openalex-snapshot
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
inferredcites →https://doi.org/10.1007/bf01305237openalex-snapshot
Pseudorandom generators for space-bounded computation
inferredcites →https://doi.org/10.1007/bf01375474openalex-snapshot
Pseudorandom bits for constant depth circuits
inferredcites →https://doi.org/10.1007/s00037-004-0187-1openalex-snapshot
The complexity of constructing pseudorandom generators from hard functions
inferredcites →https://doi.org/10.1023/a:1022949332276openalex-snapshot
Boosting and Hard-Core Set Construction
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1109/ccc.2003.1214410openalex-snapshot
Hardness vs. randomness within alternating time
inferredcites →https://doi.org/10.1109/ccc.2005.16openalex-snapshot
On Constructing Parallel Pseudorandom Generators from One-Way Functions
inferredcites →https://doi.org/10.1109/ccc.2005.17openalex-snapshot
On the Complexity of Hardness Amplification
inferredcites →https://doi.org/10.1109/sct.1995.514853openalex-snapshot
A personal view of average-case complexity
inferredcites →https://doi.org/10.1109/sfcs.1988.21923openalex-snapshot
The influence of variables on Boolean functions
inferredcites →https://doi.org/10.1109/sfcs.1995.492584openalex-snapshot
Hard-core distributions for somewhat hard problems
inferredcites →https://doi.org/10.1109/sfcs.1998.743524openalex-snapshot
Randomness vs. time: de-randomization under a uniform assumption
inferredcites →https://doi.org/10.1109/sfcs.2003.1238187openalex-snapshot
List-decoding using the XOR lemma
inferredcites →https://doi.org/10.1109/sfcs.2003.1238205openalex-snapshot
On Worst‐Case to Average‐Case Reductions for NP Problems
inferredcites →https://doi.org/10.1109/sffcs.1999.814638openalex-snapshot
Boosting and hard-core sets
inferredcites →https://doi.org/10.1137/0222061openalex-snapshot
Random-Self-Reducibility of Complete Sets
inferredcites →https://doi.org/10.1145/100216.100242openalex-snapshot
Pseudorandom generators for space-bounded computations
inferredcites →https://doi.org/10.1145/1059513.1059516openalex-snapshot
Simple extractors for all min-entropies and a new pseudorandom generator
inferredcites →https://doi.org/10.1145/195058.195190openalex-snapshot
Pseudorandomness for network algorithms
inferredcites →https://doi.org/10.1145/258533.258590openalex-snapshot
P = BPP if E requires exponential circuits
inferredcites →https://doi.org/10.1145/509907.509997openalex-snapshot
Pseudo-random generators for all hardnesses
inferredcites →https://doi.org/10.1145/509907.510015openalex-snapshot
Hardness amplification within NP
inferredcites →https://doi.org/10.1145/73007.73010openalex-snapshot
A hard-core predicate for all one-way functions
inferredcites →https://doi.org/10.1145/954092.954099openalex-snapshot
Review of Modern cryptography, probabilistic proofs and pseudorandomness algorithms and combinatorics, vol 17 by Oded Goldreich. Springer Verlag, 1999.
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
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-540-74240-1_35openalex-snapshot
Impossibility Results on Weakly Black-Box Hardness Amplification
inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_38openalex-snapshot
Improved Pseudorandom Generators for Depth 2 Circuits
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.16openalex-snapshot
On Constructing Parallel Pseudorandom Generators from One-Way Functions
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/focs.2006.13openalex-snapshot
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification
inferred← citeshttps://doi.org/10.1109/focs.2007.25openalex-snapshot
Hardness Amplification for Errorless Heuristics
inferred← citeshttps://doi.org/10.1109/focs.2007.30openalex-snapshot
Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits
inferred← citeshttps://doi.org/10.1109/focs.2007.4389512openalex-snapshot
Hardness Amplification for Errorless Heuristics
inferred← citeshttps://doi.org/10.1109/tit.2008.928988openalex-snapshot
On the Complexity of Hardness Amplification
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/smjcat0000360000040000ix000001openalex-snapshot
Special Issue on Randomness and Complexity
inferred← citeshttps://doi.org/10.1145/1060590.1060595openalex-snapshot
On uniform amplification of hardness in NP
inferred← citeshttps://doi.org/10.1145/1132516.1132583openalex-snapshot
Pseudorandom walks on regular digraphs and the RL vs. L problem
inferred← citeshttps://doi.org/10.1145/3406325.3451117openalex-snapshot
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
inferred← citeshttps://doi.org/10.4230/lipics.fscd.2020.21openalex-snapshot
Average-Case Completeness in Tag Systems
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.