On the public citation graph
Simulating BPP using a general weak random source
0 signed · 160 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/978-1-4684-2001-2_9openalex-snapshot
Reducibility among Combinatorial Problems
inferredcites →https://doi.org/10.1007/bf01200430openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf01294459openalex-snapshot
On the second eigenvalue of hypergraphs
inferredcites →https://doi.org/10.1007/bf02125896openalex-snapshot
Some extremal problems arising from discrete control processes
inferredcites →https://doi.org/10.1007/bf02579167openalex-snapshot
Independent unbiased coin flips from a correlated biased source—A finite state markov chain
inferredcites →https://doi.org/10.1007/bf02579325openalex-snapshot
Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
inferredcites →https://doi.org/10.1016/0022-0000(79)90044-8openalex-snapshot
Universal classes of hash functions
inferredcites →https://doi.org/10.1016/0022-0000(81)90040-4openalex-snapshot
Explicit constructions of linear-sized superconcentrators
inferredcites →https://doi.org/10.1016/0022-0000(86)90044-9openalex-snapshot
Generating quasi-random sequences from semi-random sources
inferredcites →https://doi.org/10.1016/0022-0000(88)90035-9openalex-snapshot
Expanders, randomness, or time versus space
inferredcites →https://doi.org/10.1016/0022-314x(80)90084-0openalex-snapshot
Probabilistic algorithm for testing primality
inferredcites →https://doi.org/10.1016/0095-8956(85)90092-9openalex-snapshot
λ1, Isoperimetric inequalities for graphs, and superconcentrators
inferredcites →https://doi.org/10.1016/0304-3975(94)90251-8openalex-snapshot
On the power of multi-prover interactive protocols
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/0890-5401(87)90023-xopenalex-snapshot
On using deterministic functions to reduce randomness in probabilistic algorithms
inferredcites →https://doi.org/10.1109/fscs.1990.89520openalex-snapshot
Nondeterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1109/sct.1993.336517openalex-snapshot
NP-complete problems have a version that's hard to approximate
inferredcites →https://doi.org/10.1109/sfcs.1984.715945openalex-snapshot
Generating Quasi-Random Sequences From Slightly-Random Sources
inferredcites →https://doi.org/10.1109/sfcs.1985.45openalex-snapshot
Random polynomial time is equal to slightly-random polynomial time
inferredcites →https://doi.org/10.1109/sfcs.1985.55openalex-snapshot
The bit extraction problem or t-resilient 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.1991.185341openalex-snapshot
Approximating clique is almost NP-complete
inferredcites →https://doi.org/10.1109/sfcs.1991.185351openalex-snapshot
Simulating BPP using a general weak random source
inferredcites →https://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferredcites →https://doi.org/10.1109/sfcs.1992.267824openalex-snapshot
Probabilistic checking of proofs; a new characterization of NP
inferredcites →https://doi.org/10.1109/sfcs.1994.365688openalex-snapshot
Computing with very weak random sources
inferredcites →https://doi.org/10.1137/0217014openalex-snapshot
Privacy Amplification by Public Discussion
inferredcites →https://doi.org/10.1137/0217015openalex-snapshot
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
inferredcites →https://doi.org/10.1137/0605030openalex-snapshot
Explicit Concentrators from Generalized N -Gons
inferredcites →https://doi.org/10.1145/102782.102783openalex-snapshot
A random polynomial-time algorithm for approximating the volume of convex bodies
inferredcites →https://doi.org/10.1145/167088.167163openalex-snapshot
Expanders that beat the eigenvalue bound
inferredcites →https://doi.org/10.1145/167088.167166openalex-snapshot
Efficient construction of a small hitting set for combinatorial rectangles in high dimension
inferredcites →https://doi.org/10.1145/195058.195129openalex-snapshot
Improved non-approximability results
inferredcites →https://doi.org/10.1145/225058.225188openalex-snapshot
Explicit dispersers with polylog degree
inferredcites →https://doi.org/10.1145/28395.28413openalex-snapshot
Efficiency considerations in using semi-random sources
inferredcites →https://doi.org/10.1145/73007.73009openalex-snapshot
Pseudo-random generation from one-way functions
inferredcites →https://doi.org/10.1214/aoms/1177692552openalex-snapshot
The Efficient Construction of an Unbiased Random Sequence
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/(sici)1098-2418(199712)11:4<315::aid-rsa3>3.0.co;2-1openalex-snapshot
Tiny families of functions with random properties: A quality-size trade-off for hashing
inferred← citeshttps://doi.org/10.1002/rsa.20207openalex-snapshot
How to get more mileage from randomness extractors
inferred← citeshttps://doi.org/10.1006/jcss.2000.1730openalex-snapshot
Pseudorandom Generators without the XOR Lemma
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/11533719_35openalex-snapshot
A Note on Zero Error Algorithms Having Oracle Access to One NP Query
inferred← citeshttps://doi.org/10.1007/11681878_31openalex-snapshot
Separating Sources for Encryption and Secret Sharing
inferred← citeshttps://doi.org/10.1007/11786986_9openalex-snapshot
Deterministic Extractors for Independent-Symbol Sources
inferred← citeshttps://doi.org/10.1007/11787006_18openalex-snapshot
On the Impossibility of Extracting Classical Randomness Using a Quantum Computer
inferred← citeshttps://doi.org/10.1007/3-540-44679-6_53openalex-snapshot
On Testing for Zero Polynomials by a Set of Points with Bounded Precision
inferred← citeshttps://doi.org/10.1007/3-540-48224-5_25openalex-snapshot
New Imperfect Random Source with Applications to Coin-Flipping
inferred← citeshttps://doi.org/10.1007/3-540-69053-0_14openalex-snapshot
Smooth Entropy and Rényi Entropy
inferred← citeshttps://doi.org/10.1007/978-3-030-17653-2_19openalex-snapshot
Correlated-Source Extractors and Cryptography with Correlated-Random Tapes
inferred← citeshttps://doi.org/10.1007/978-3-030-36033-7_13openalex-snapshot
Estimating Gaps in Martingales and Applications to Coin-Tossing: Constructions and Hardness
inferred← citeshttps://doi.org/10.1007/978-3-030-50026-9_29openalex-snapshot
The Untold Story of $$\mathsf {SBP}$$
inferred← citeshttps://doi.org/10.1007/978-3-0348-9110-3_2openalex-snapshot
Transparent Proofs and Limits to Approximation
inferred← citeshttps://doi.org/10.1007/978-3-319-57048-8_4openalex-snapshot
The Many Entropies in One-Way Functions
inferred← citeshttps://doi.org/10.1007/978-3-540-27821-4_30openalex-snapshot
Improved Randomness Extraction from Two Independent Sources
inferred← citeshttps://doi.org/10.1007/978-3-540-30576-7_31openalex-snapshot
Error Correction in the Bounded Storage Model
inferred← citeshttps://doi.org/10.1007/978-3-540-45146-4_4openalex-snapshot
On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model
inferred← citeshttps://doi.org/10.1007/978-3-540-45198-3_22openalex-snapshot
On Extracting Private Randomness over a Public Channel
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-70936-7_1openalex-snapshot
Does Privacy Require True Randomness?
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_29openalex-snapshot
Tight Bounds for Hashing Block Sources
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_44openalex-snapshot
Extractors for Three Uneven-Length Sources
inferred← citeshttps://doi.org/10.1007/978-3-540-95891-8_22openalex-snapshot
Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes
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-14496-7_6openalex-snapshot
On the Security of Pseudorandomized Information-Theoretically Secure Schemes
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-16280-0_10openalex-snapshot
Distinguishing Distributions Using Chernoff Information
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-32009-5_29openalex-snapshot
Differential Privacy with Imperfect Randomness
inferred← citeshttps://doi.org/10.1007/978-3-642-42033-7_14openalex-snapshot
Function-Private Subspace-Membership Encryption and Its Applications
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-48000-7_23openalex-snapshot
Privacy with Imperfect Randomness
inferred← citeshttps://doi.org/10.1007/bf01200907openalex-snapshot
Efficient construction of a small hitting set for combinatorial rectangles in high dimension
inferred← citeshttps://doi.org/10.1007/bf01940869openalex-snapshot
Introduction to special issue on randomized and derandomized algorithms
inferred← citeshttps://doi.org/10.1007/bfb0052243openalex-snapshot
Unconditional security against memory-bounded adversaries
inferred← citeshttps://doi.org/10.1007/bfb0054363openalex-snapshot
Extractors for weak random sources and their applications
inferred← citeshttps://doi.org/10.1007/s00145-003-0237-xopenalex-snapshot
Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model
inferred← citeshttps://doi.org/10.1007/s00145-013-9174-5openalex-snapshot
A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy
inferred← citeshttps://doi.org/10.1007/s001459910005openalex-snapshot
Randomness versus Fault-Tolerance
inferred← citeshttps://doi.org/10.1007/s00493-007-0053-2openalex-snapshot
Lossless Condensers, Unbalanced Expanders, And Extractors
inferred← citeshttps://doi.org/10.1007/s00493-008-2259-3openalex-snapshot
Deterministic extractors for affine sources over large fields
inferred← citeshttps://doi.org/10.1007/s004930050049openalex-snapshot
Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications
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.1016/j.jcss.2005.05.010openalex-snapshot
Extractors from Reed–Muller codes
inferred← citeshttps://doi.org/10.1016/j.jcss.2010.06.014openalex-snapshot
Deterministic extractors for small-space sources
inferred← citeshttps://doi.org/10.1016/s0020-0190(99)00011-3openalex-snapshot
A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00429-2openalex-snapshot
On testing for zero polynomials by a set of points with bounded precision
inferred← citeshttps://doi.org/10.1049/iet-ifs.2015.0007openalex-snapshot
Security of weak secrets based cryptographic primitives via the Rényi entropy
inferred← citeshttps://doi.org/10.1093/comjnl/bxt097openalex-snapshot
On Unconditional -Security of Private Key Encryption
inferred← citeshttps://doi.org/10.1103/revmodphys.89.015004openalex-snapshot
Quantum random number generators
inferred← citeshttps://doi.org/10.1109/18.841191openalex-snapshot
Extraction of optimally unbiased bits from a biased source
inferred← citeshttps://doi.org/10.1109/allerton.2013.6736515openalex-snapshot
Double hashing thresholds via local weak convergence
inferred← citeshttps://doi.org/10.1109/ccc.1996.507690openalex-snapshot
Zero knowledge and the chromatic number
inferred← citeshttps://doi.org/10.1109/ccc.2006.24openalex-snapshot
How to Get More Mileage from Randomness Extractors
inferred← citeshttps://doi.org/10.1109/ccc.2007.38openalex-snapshot
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes
inferred← citeshttps://doi.org/10.1109/ccc.2010.14openalex-snapshot
Simple Affine Extractors Using Dimension Expansion
inferred← citeshttps://doi.org/10.1109/focs.2004.21openalex-snapshot
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed
inferred← citeshttps://doi.org/10.1109/focs.2004.29openalex-snapshot
Extracting Randomness Using Few Independent Sources
inferred← citeshttps://doi.org/10.1109/focs.2004.44openalex-snapshot
On the (Im)possibility of Cryptography with Imperfect Randomness
inferred← citeshttps://doi.org/10.1109/focs.2009.61openalex-snapshot
2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness
inferred← citeshttps://doi.org/10.1109/focs.2011.49openalex-snapshot
Balls and Bins: Smaller Hash Families and Faster Evaluation
inferred← citeshttps://doi.org/10.1109/focs.2017.74openalex-snapshot
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00025openalex-snapshot
Improved Hardness of Approximating k-Clique under ETH
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.743500openalex-snapshot
Oblivious transfer with a memory-bounded receiver
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892006openalex-snapshot
Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892008openalex-snapshot
Extracting randomness via repeated condensing
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892063openalex-snapshot
Extracting randomness from samplable distributions
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959940openalex-snapshot
Extractors from Reed-Muller codes
inferred← citeshttps://doi.org/10.1109/sfcs.2002.1181962openalex-snapshot
On the (non)universality of the one-time pad
inferred← citeshttps://doi.org/10.1109/sfcs.2005.31openalex-snapshot
Deterministic Extractors for Affine Sources over Large Fields
inferred← citeshttps://doi.org/10.1109/sffcs.1999.814619openalex-snapshot
Hardness of approximating Σ/sub 2//sup p/ minimization problems
inferred← citeshttps://doi.org/10.1109/tifs.2017.2780802openalex-snapshot
Differential Privacy With Bias-Control Limited Sources
inferred← citeshttps://doi.org/10.1109/tit.2010.2079012openalex-snapshot
Deterministic Extractors for Independent-Symbol Sources
inferred← citeshttps://doi.org/10.1109/tit.2012.2216978openalex-snapshot
On the Security of Pseudorandomized Information-Theoretically Secure Schemes
inferred← citeshttps://doi.org/10.1109/tit.2025.3605160openalex-snapshot
Nearly-Linear Time Seeded Extractors With Short Seeds
inferred← citeshttps://doi.org/10.1137/1.9781611974331.ch105openalex-snapshot
Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders
inferred← citeshttps://doi.org/10.1137/100814421openalex-snapshot
Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions
inferred← citeshttps://doi.org/10.1137/18m1166869openalex-snapshot
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
inferred← citeshttps://doi.org/10.1137/s089548019427634xopenalex-snapshot
A Randomness-Rounds Tradeoff in Private Computation
inferred← citeshttps://doi.org/10.1137/s0895480197329508openalex-snapshot
Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
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.1145/1132516.1132589openalex-snapshot
Extractors for a constant number of polynomially small min-entropy independent sources
inferred← citeshttps://doi.org/10.1145/1132516.1132612openalex-snapshot
Linear degree extractors and the inapproximability of max clique and chromatic number
inferred← citeshttps://doi.org/10.1145/1132516.1132613openalex-snapshot
Deterministic extractors for small-space sources
inferred← citeshttps://doi.org/10.1145/1324215.1324225openalex-snapshot
The unified theory of pseudorandomness
inferred← citeshttps://doi.org/10.1145/1538902.1538904openalex-snapshot
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
inferred← citeshttps://doi.org/10.1145/167088.167166openalex-snapshot
Efficient construction of a small hitting set for combinatorial rectangles in high dimension
inferred← citeshttps://doi.org/10.1145/1806689.1806750openalex-snapshot
Efficiency improvements in constructing pseudorandom generators from one-way functions
inferred← citeshttps://doi.org/10.1145/1993574.1993623openalex-snapshot
Pseudorandom financial derivatives
inferred← citeshttps://doi.org/10.1145/273865.273915openalex-snapshot
Explicit OR-dispersers with polylogarithmic degree
inferred← citeshttps://doi.org/10.1145/277697.277710openalex-snapshot
Amortizing randomness in private multiparty computations
inferred← citeshttps://doi.org/10.1145/301250.301292openalex-snapshot
Extracting all the randomness and reducing the error in Trevisan's extractors
inferred← citeshttps://doi.org/10.1145/301250.301397openalex-snapshot
Pseudorandom generators without the XOR Lemma (extended abstract)
inferred← citeshttps://doi.org/10.1145/3294052.3319686openalex-snapshot
Topology Dependent Bounds For FAQs
inferred← citeshttps://doi.org/10.1145/380752.380790openalex-snapshot
Loss-less condensers, unbalanced expanders, and extractors
inferred← citeshttps://doi.org/10.31274/rtd-180813-10541openalex-snapshot
The complexity of parameters for probabilistic and quantum computation
inferred← citeshttps://doi.org/10.3390/a13060146openalex-snapshot
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
inferred← citeshttps://doi.org/10.3929/ethz-a-001806220openalex-snapshot
Entropy measures and unconditional security in cryptography
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2020.1openalex-snapshot
Near-optimal erasure list-decodable codes
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2009.2340openalex-snapshot
Randomness extractors -- applications and constructions
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2022.90openalex-snapshot
On Lower Bounds of Approximating Parameterized $k$-Clique
inferred← citeshttps://doi.org/10.48550/arxiv.1208.5918openalex-snapshot
Uncertainty relations for multiple measurements with applications
inferred← citeshttps://doi.org/10.48550/arxiv.1311.5622openalex-snapshot
Improved Extractors for Affine Lines
inferred← citeshttps://doi.org/10.48550/arxiv.quant-ph/0612012openalex-snapshot
On the impossibility of extracting classical randomness using a quantum computer
inferred← citeshttps://doi.org/10.5555/1496770.1496857openalex-snapshot
On risks of using cuckoo hashing with simple universal hash classes
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.