On the power of two-point based sampling
From MaRDI portal
Publication:1120201
DOI10.1016/0885-064X(89)90015-0zbMath0672.60105OpenAlexW2019038806MaRDI QIDQ1120201
Publication date: 1989
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0885-064x(89)90015-0
Related Items
Randomized OBDD-based graph algorithms, A combinatorial error bound for \(t\)-point-based sampling, Efficient constructions of Hitting Sets for systems of linear functions, The relative exponential time complexity of approximate counting satisfying assignments, A simple analysis of the error probability of two-point based sampling, Randomized OBDD-Based Graph Algorithms, A connection between random variables and latin \(k\)-cubes, Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8, On the oracle complexity of factoring integers, Efficient construction of a small hitting set for combinatorial rectangles in high dimension, Simulating BPP using a general weak random source, The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments, Deterministic Massively Parallel Connectivity, Universal Hashing via Integer Arithmetic Without Primes, Revisited, Unnamed Item, Quasi-random rumor spreading: reducing randomness can be costly, A fast output-sensitive algorithm for Boolean matrix multiplication, Simple fast parallel hashing, Local randomness in pseudorandom sequences, Bounded Independence Plus Noise Fools Products, Pseudorandom generators without the XOR lemma, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Realistic analysis of some randomized algorithms, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Polynomial hash functions are reliable, On the complexity of constructing pseudorandom functions (especially when they don't exist), In a World of P=BPP, A Sample of Samplers: A Computational Perspective on Sampling, Reducing complexity assumptions for statistically-hiding commitment, \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\), Improved algorithms via approximations of probability distributions, A Time-Randomness Tradeoff for Quasi-Random Rumour Spreading, Robust characterizations of k -wise independence over product spaces and related testing results, Extracting randomness: A survey and new constructions, Randomness in interactive proofs, Provably good pattern generators for a random pattern test, A PCP of proximity for real algebraic polynomials
Cites Work
- Unnamed Item
- Eigenvalues and expanders
- Universal classes of hash functions
- On a set of almost deterministic k-independent random variables
- How to share a secret
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- On a Sequence of Almost Deterministic Pairwise Independent Random Variables
