Small-Bias Probability Spaces: Efficient Constructions and Applications

DOI10.1137/0222053zbMath0776.60014OpenAlexW2019807548MaRDI 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

zbMATH Keywords

discrepancyrandomized algorithmsderandomizationVLSI circuit testing

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Fault detection; testing in circuits and networks (94C12) Randomized algorithms (68W20)

Related Items (only showing first 100 items - show all)

Almost Optimal Cover-Free Families ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Unnamed Item ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions ⋮ Constant-Round Interactive Proof Systems for AC0[2 and NC1] ⋮ Deterministic Massively Parallel Connectivity ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ Random sources in private computation ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Bit security as computational cost for winning games with high probability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs ⋮ Constructions of strongly regular Cayley graphs derived from weakly regular bent functions ⋮ New bounds for the Moser‐Tardos distribution ⋮ Unnamed Item ⋮ Amplification and Derandomization without Slowdown ⋮ Unnamed Item ⋮ Optimal explicit small-depth formulas for the coin problem ⋮ Unnamed Item ⋮ Randomness Extraction Via δ-Biased Masking in the Presence of a Quantum Attacker ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Learning a circuit by injecting values ⋮ Short Proofs Are Hard to Find ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Unnamed Item ⋮ Optimal $\varepsilon$-Biased Sets with Just a Little Randomness ⋮ Fast Interactive Coding against Adversarial Noise ⋮ Explicit Near-Ramanujan Graphs of Every Degree ⋮ Unnamed Item ⋮ More efficient PAC-learning of DNF with membership queries under the uniform distribution ⋮ Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes ⋮ On the optimality of quantum encryption schemes ⋮ Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations ⋮ Randomized OBDD-based graph algorithms ⋮ MODp-tests, almost independence and small probability spaces ⋮ Derandomizing restricted isometries via the Legendre symbol ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ Secure computation using leaky correlations (asymptotically optimal constructions) ⋮ The probabilistic method yields deterministic parallel algorithms ⋮ New techniques and tighter bounds for local computation algorithms ⋮ The cell probe complexity of succinct data structures ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Consensus Patterns (Probably) Has no EPTAS ⋮ On the extremal combinatorics of the Hamming space ⋮ A dichotomy for local small-bias generators ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Interactive communication with unknown noise rate ⋮ Deterministic constructions of high-dimensional sets with small dispersion ⋮ Randomized OBDD-Based Graph Algorithms ⋮ On the ring-LWE and polynomial-LWE problems ⋮ Cryptographic hardness of random local functions. Survey ⋮ Matrix rigidity of random Toeplitz matrices ⋮ Improved bounds on the an-complexity of \(O(1)\)-linear functions ⋮ A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8 ⋮ Entropy of Weight Distributions of Small-Bias Spaces and Pseudobinomiality ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Efficiently correcting matrix products ⋮ On deterministic approximation of DNF ⋮ Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions ⋮ Randomized geometric algorithms and pseudorandom generators ⋮ Defaults and relevance in model-based reasoning ⋮ Efficiently Correcting Matrix Products ⋮ (De)randomized construction of small sample spaces in \(\mathcal{NC}\) ⋮ Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields] ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Checking the correctness of memories ⋮ Unnamed Item ⋮ The isomorphism conjecture for constant depth reductions ⋮ Almost \(k\)-wise independence and hard Boolean functions. ⋮ Locating and detecting arrays for interaction faults ⋮ Unnamed Item ⋮ On rigid matrices and \(U\)-polynomials ⋮ On the derandomization of the graph test for homomorphism over groups ⋮ Unnamed Item ⋮ Parameterized random complexity ⋮ More on average case vs approximation complexity ⋮ Hierarchy theorems for property testing ⋮ Unnamed Item ⋮ Simple and efficient batch verification techniques for verifiable delay functions ⋮ On deterministic sketching and streaming for sparse recovery and norm estimation ⋮ Cryptographic hash functions from sequences of lifted Paley graphs ⋮ A one-time stegosystem and applications to efficient covert communication ⋮ Revisiting iterated attacks in the context of decorrelation theory ⋮ Small Sample Spaces Cannot Fool Low Degree Polynomials ⋮ Hierarchy Theorems for Property Testing ⋮ Deterministic parallel algorithms for bilinear objective functions ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ On quasilinear-time complexity theory ⋮ Constructions of almost secure frameproof codes with applications to fingerprinting schemes ⋮ Bounded Independence Plus Noise Fools Products ⋮ Preserving Randomness for Adaptive Algorithms

This page was built for publication: Small-Bias Probability Spaces: Efficient Constructions and Applications