On the public citation graph
Randomness in interactive proofs
0 signed · 91 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-16486-3_108openalex-snapshot
Expanders, randomness, or time versus space
inferredcites →https://doi.org/10.1007/3-540-52846-6_73openalex-snapshot
Structural complexity theory: Recent surprises
inferredcites →https://doi.org/10.1007/bf01585569openalex-snapshot
The complexity of approximating a nonlinear program
inferredcites →https://doi.org/10.1016/0020-0190(87)90232-8openalex-snapshot
Does co-NP have short interactive proofs?
inferredcites →https://doi.org/10.1016/0020-0190(94)00171-topenalex-snapshot
Lower bounds for sampling algorithms for estimating the average
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(88)90028-1openalex-snapshot
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
inferredcites →https://doi.org/10.1016/0022-0000(88)90035-9openalex-snapshot
Expanders, randomness, or time versus space
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.1016/0890-5401(89)90053-9openalex-snapshot
Proving properties of interactive proofs by a generalized counting technique
inferredcites →https://doi.org/10.1109/fscs.1990.89518openalex-snapshot
Algebraic methods for interactive proof systems
inferredcites →https://doi.org/10.1109/fscs.1990.89550openalex-snapshot
Security preserving amplification of hardness
inferredcites →https://doi.org/10.1109/istcs.1993.253462openalex-snapshot
Interactive proofs and approximation: reductions from two provers in one round
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.1988.21944openalex-snapshot
New algorithms for finding irreducible polynomials over finite fields
inferredcites →https://doi.org/10.1109/sfcs.1989.63449openalex-snapshot
Dispersers, deterministic amplification, and weak random sources
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.1142/9789814354363_0002openalex-snapshot
The Complexity of Approximating a Nonlinear Program
inferredcites →https://doi.org/10.1145/100216.100242openalex-snapshot
Pseudorandom generators for space-bounded computations
inferredcites →https://doi.org/10.1145/100216.100270openalex-snapshot
Pseudo-random generators under uniform assumptions
inferredcites →https://doi.org/10.1145/116825.116852openalex-snapshot
Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
inferredcites →https://doi.org/10.1145/12130.12137openalex-snapshot
Private coins versus public coins in interactive proof systems
inferredcites →https://doi.org/10.1145/12130.12154openalex-snapshot
Explicit expanders and the Ramanujan conjectures
inferredcites →https://doi.org/10.1145/129712.129783openalex-snapshot
Two-prover one-round proof systems
inferredcites →https://doi.org/10.1145/167088.167172openalex-snapshot
On the hardness of approximating minimization problems
inferredcites →https://doi.org/10.1145/22145.22192openalex-snapshot
Trading group theory for randomness
inferredcites →https://doi.org/10.1145/28395.28410openalex-snapshot
Deterministic simulation in LOGSPACE
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/800157.805047openalex-snapshot
The complexity of theorem-proving procedures
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.3240030308openalex-snapshot
Simple Constructions of Almost k‐wise Independent Random Variables
inferred← citeshttps://doi.org/10.1006/jcss.1998.1605openalex-snapshot
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems
inferred← citeshttps://doi.org/10.1006/jcss.1999.1686openalex-snapshot
On the Limits of Nonapproximability of Lattice Problems
inferred← citeshttps://doi.org/10.1007/11830924_37openalex-snapshot
Randomness-Efficient Sampling Within NC 1
inferred← citeshttps://doi.org/10.1007/3-540-45726-7_15openalex-snapshot
Randomness-Optimal Characterization of Two NP Proof Systems
inferred← citeshttps://doi.org/10.1007/3-540-49543-6_5openalex-snapshot
On the Derandomization of Space-Bounded Computations
inferred← citeshttps://doi.org/10.1007/3-540-63165-8_225openalex-snapshot
Randomness-efficient non-interactive zero knowledge
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_5openalex-snapshot
A Taxonomy of Proof Systems
inferred← citeshttps://doi.org/10.1007/978-3-319-99660-8_14openalex-snapshot
Efficient Rational Proofs with Strong Utility-Gap Guarantees
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-642-22006-7_49openalex-snapshot
A PCP Characterization of AM
inferred← citeshttps://doi.org/10.1007/978-3-642-22670-0_24openalex-snapshot
A Sample of Samplers: A Computational Perspective on Sampling
inferred← citeshttps://doi.org/10.1007/978-3-642-22670-0_36openalex-snapshot
Another Motivation for Reducing the Randomness Complexity of Algorithms
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-49099-0_13openalex-snapshot
Interactive Coding for Interactive Proofs
inferred← citeshttps://doi.org/10.1007/s00037-013-0071-yopenalex-snapshot
Derandomized Parallel Repetition Theorems for Free Games
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.1109/ccc.2010.12openalex-snapshot
Derandomized Parallel Repetition Theorems for Free Games
inferred← citeshttps://doi.org/10.1109/ccc.2011.15openalex-snapshot
Approximation Algorithms for QMA-Complete Problems
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.2011.93openalex-snapshot
The Randomness Complexity of Parallel Repetition
inferred← citeshttps://doi.org/10.1109/focs.2018.00015openalex-snapshot
Simple Optimal Hitting Sets for Small-Success RL
inferred← citeshttps://doi.org/10.1109/sfcs.1994.365687openalex-snapshot
Randomness-efficient oblivious sampling
inferred← citeshttps://doi.org/10.1109/sfcs.1995.492573openalex-snapshot
Free bits, PCPs and non-approximability-towards tight results
inferred← citeshttps://doi.org/10.1137/080734030openalex-snapshot
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
inferred← citeshttps://doi.org/10.1137/110842272openalex-snapshot
Approximation Algorithms for QMA-Complete Problems
inferred← citeshttps://doi.org/10.1137/19m1268707openalex-snapshot
Simple Optimal Hitting Sets for Small-Success RL
inferred← citeshttps://doi.org/10.1137/s0097539794273083openalex-snapshot
An $\NC$ Algorithm for Minimum Cuts
inferred← citeshttps://doi.org/10.1137/s0097539796302531openalex-snapshot
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
inferred← citeshttps://doi.org/10.1137/s089548010135274xopenalex-snapshot
Amortizing Randomness in Private Multiparty Computations
inferred← citeshttps://doi.org/10.1145/1374376.1374460openalex-snapshot
Uniform direct product theorems
inferred← citeshttps://doi.org/10.1145/167088.167162openalex-snapshot
More deterministic simulation in logspace
inferred← citeshttps://doi.org/10.1145/225058.225140openalex-snapshot
Polynomial time approximation schemes for dense instances of NP -hard problems
inferred← citeshttps://doi.org/10.1145/237814.237878openalex-snapshot
Randomness-optimal sampling, extractors, and constructive leader election
inferred← citeshttps://doi.org/10.1145/248052.248089openalex-snapshot
Randomness in private computations
inferred← citeshttps://doi.org/10.1145/277697.277710openalex-snapshot
Amortizing randomness in private multiparty computations
inferred← citeshttps://doi.org/10.1145/333979.333984openalex-snapshot
An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
inferred← citeshttps://doi.org/10.1145/3564246.3585189openalex-snapshot
Hardness Self-Amplification: Simplified, Optimized, and Unified
inferred← citeshttps://doi.org/10.1145/3798129.3800898openalex-snapshot
Range Avoidance, Arthur-Merlin, and TFNP
inferred← citeshttps://doi.org/10.1515/9780823295708-025openalex-snapshot
CHAPTER NOTES AND REFERENCES
inferred← citeshttps://doi.org/10.1515/9783110203738.455openalex-snapshot
Chapter 8 Notes and References
inferred← citeshttps://doi.org/10.3390/e27070757openalex-snapshot
Graph-Theoretic Limits of Distributed Computation: Entropy, Eigenvalues, and Chromatic Numbers
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2018.43openalex-snapshot
Preserving Randomness for Adaptive Algorithms
inferred← citeshttps://doi.org/10.48550/arxiv.1301.2632openalex-snapshot
Approximation, Proof Systems, and Correlations in a Quantum World
inferred← citeshttps://doi.org/10.5040/9780755625963.0007openalex-snapshot
Chapter Notes and References
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.