Small-Bias Probability Spaces: Efficient Constructions and Applications
From MaRDI portal
Publication:3137711
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
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)
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 ⋮ Approximation algorithm for DNF under distributions with limited independence ⋮ Improved parallel approximation of a class of integer programming problems ⋮ Efficient branching programs for quantum hash functions generated by small-biased sets ⋮ Small-bias is not enough to hit read-once CNF ⋮ The communication complexity of addition ⋮ Symmetric LDPC codes and local testing ⋮ Testing periodicity ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets ⋮ Extractors from Reed-Muller codes ⋮ [https://portal.mardi4nfdi.de/wiki/Publication:4521547 Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma] ⋮ Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification ⋮ Interactive Coding for Interactive Proofs ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ On the capacity of Boolean graph formulæ ⋮ Secure sequential transmission of quantum information ⋮ Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set ⋮ Three XOR-Lemmas — An Exposition ⋮ Public-coin statistical zero-knowledge batch verification against malicious verifiers ⋮ Capacity of Interactive Communication over Erasure Channels and Channels with Feedback ⋮ Almost \(k\)-wise independence versus \(k\)-wise independence ⋮ Approximating hyper-rectangles: Learning and pseudorandom sets ⋮ Unnamed Item ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ Improved algorithms via approximations of probability distributions ⋮ Analysis of properties of quantum hashing ⋮ Robust characterizations of k -wise independence over product spaces and related testing results ⋮ Bounds and constructions for the star-discrepancy via \(\delta\)-covers ⋮ Extracting randomness: A survey and new constructions ⋮ Approximate swapped matching. ⋮ On hitting-set generators for polynomials that vanish rarely ⋮ On the decisional complexity of problems over the reals ⋮ Pseudorandom Functions: Three Decades Later ⋮ 3SUM, 3XOR, triangles
This page was built for publication: Small-Bias Probability Spaces: Efficient Constructions and Applications
