Small-Bias Probability Spaces: Efficient Constructions and Applications
From MaRDI portal
Publication:3137711
DOI10.1137/0222053zbMath0776.60014MaRDI QIDQ3137711
Moni Naor, Joseph (Seffi) Naor
Publication date: 10 October 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222053
60E15: Inequalities; stochastic orderings
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
60C05: Combinatorial probability
94C12: Fault detection; testing in circuits and networks
68W20: Randomized algorithms
Related Items
Unnamed Item, Hierarchy Theorems for Property Testing, Randomness Extraction Via δ-Biased Masking in the Presence of a Quantum Attacker, Learning a circuit by injecting values, More on average case vs approximation complexity, Hierarchy theorems for property testing, Testing periodicity, The isomorphism conjecture for constant depth reductions, On quasilinear-time complexity theory, Approximation algorithm for DNF under distributions with limited independence, Improved parallel approximation of a class of integer programming problems, Almost \(k\)-wise independence versus \(k\)-wise independence, Defaults and relevance in model-based reasoning, Approximating hyper-rectangles: Learning and pseudorandom sets, Sparse hard sets for P: Resolution of a conjecture of Hartmanis, Extracting randomness: A survey and new constructions, The probabilistic method yields deterministic parallel algorithms, (De)randomized construction of small sample spaces in \(\mathcal{NC}\), Almost \(k\)-wise independence and hard Boolean functions., Improved algorithms via approximations of probability distributions, On the capacity of Boolean graph formulæ, Approximate swapped matching., On the decisional complexity of problems over the reals, More efficient PAC-learning of DNF with membership queries under the uniform distribution, On the extremal combinatorics of the Hamming space, On deterministic approximation of DNF, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Randomized geometric algorithms and pseudorandom generators, The cell probe complexity of succinct data structures, Locating and detecting arrays for interaction faults, On the derandomization of the graph test for homomorphism over groups, Extractors from Reed-Muller codes, Bounds and constructions for the star-discrepancy via \(\delta\)-covers, Three XOR-Lemmas — An Exposition, On the optimality of quantum encryption schemes, Small Sample Spaces Cannot Fool Low Degree Polynomials
