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, Optimal $\varepsilon$-Biased Sets with Just a Little Randomness, Fast Interactive Coding against Adversarial Noise, Learning a circuit by injecting values, DNF sparsification and a faster deterministic counting algorithm, Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields], Pseudorandom generators for combinatorial checkerboards, More on average case vs approximation complexity, Hierarchy theorems for property testing, Revisiting iterated attacks in the context of decorrelation theory, 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, Parameterized random complexity, Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets, 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, On deterministic sketching and streaming for sparse recovery and norm estimation, A one-time stegosystem and applications to efficient covert communication, Extractors from Reed-Muller codes, Bounds and constructions for the star-discrepancy via \(\delta\)-covers, Robust characterizations of k -wise independence over product spaces and related testing results, Three XOR-Lemmas — An Exposition, On the optimality of quantum encryption schemes, Small Sample Spaces Cannot Fool Low Degree Polynomials