Small-Bias Probability Spaces: Efficient Constructions and Applications
From MaRDI portal
Recommendations
- Simple Constructions of Almost k-wise Independent Random Variables
- Sample spaces with small bias on neighborhoods and error-correcting communication protocols
- Almost \(k\)-wise independent sample spaces and their cryptologic applications
- On the relationship between -biased random variables and -dependent random variables
- Optimal -biased sets with just a little randomness
Cited in
(only showing first 100 items - show all)- 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
- A note on the influence of an \(\epsilon\)-biased random source
- Bounds on sample space size for matrix product verification
- On the relationship between -biased random variables and -dependent random variables
- 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
- Randomized OBDD-based graph algorithms
- Secure computation using leaky correlations (asymptotically optimal constructions)
- On the ring-LWE and polynomial-LWE problems
- Matrix rigidity of random Toeplitz matrices
- A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
- Constructions of almost secure frameproof codes with applications to fingerprinting schemes
- 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
- Efficient branching programs for quantum hash functions generated by small-biased sets
- A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
- Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets
- Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification
- Placing conditional disclosure of secrets in the communication complexity universe
- Public-coin statistical zero-knowledge batch verification against malicious verifiers
- On hitting-set generators for polynomials that vanish rarely
- Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes
- Succinct non-interactive arguments via linear interactive proofs
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
- Deterministic constructions of high-dimensional sets with small dispersion
- Improved bounds on the an-complexity of \(O(1)\)-linear functions
- Analysis of properties of quantum hashing
- The cell probe complexity of succinct data structures
- Efficiently correcting matrix products
- 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
- 3SUM, 3XOR, triangles
- New techniques and tighter bounds for local computation algorithms
- Simple and efficient batch verification techniques for verifiable delay functions
- Interactive Coding for Interactive Proofs
- Robust characterizations of k-wise independence over product spaces and related testing results
- Small-bias sets from extended norm-trace codes
- Efficiently correcting matrix products
- Balancing output length and query bound in hardness preserving constructions of pseudorandom functions
- Linear Time Constructions of Some d-Restriction Problems
- Derandomizing restricted isometries via the Legendre symbol
- Cryptographic hash functions from sequences of lifted Paley graphs
- Three XOR-lemmas -- an exposition
- A dichotomy for local small-bias generators
- Fast pseudorandom functions based on expander graphs
- Entropy of weight distributions of small-bias spaces and pseudobinomiality
- Cryptographic hardness of random local functions. Survey
- On the optimality of quantum encryption schemes
- Consensus patterns (probably) has no EPTAS
- Randomized OBDD-based graph algorithms
- Small Sample Spaces Cannot Fool Low Degree Polynomials
- DNF sparsification and a faster deterministic counting algorithm
- Small-Bias Spaces for Group Products
- Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields
- Pseudorandom generators for combinatorial checkerboards
- Simple Constructions of Almost k-wise Independent Random Variables
- Constructing Small Sample Spaces Satisfying Given Constraints
- More on average case vs approximation complexity
- Hierarchy theorems for property testing
- scientific article; zbMATH DE number 1496576 (Why is no real title available?)
- Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
- Pseudorandomness via the discrete Fourier transform
- \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
- Revisiting iterated attacks in the context of decorrelation theory
- Some limitations of the sum of small-bias distributions
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Bounded independence plus noise fools products
- Hierarchy theorems for property testing
- Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
- Capacity of interactive communication over erasure channels and channels with feedback
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- Small bias requires large formulas
- A quadratic size-hierarchy theorem for small-depth multilinear formulas
- Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
- Preserving randomness for adaptive algorithms
- On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
- Pseudorandom functions: three decades later
- Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations
- \(\mathrm{MOD}_p\)-tests, almost independence and small probability spaces (extended abstract)
- Quantified Derandomization: How to Find Water in the Ocean
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- Short Proofs Are Hard to Find
- Fourier bounds and pseudorandom generators for product tests
This page was built for publication: Small-Bias Probability Spaces: Efficient Constructions and Applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3137711)
