Amplification and Derandomization without Slowdown
From MaRDI portal
Publication:5129234
DOI10.1137/17M1110596zbMath1476.68304arXiv1509.08123OpenAlexW3092632169MaRDI QIDQ5129234
Dana Moshkovitz, Ofer Grossman
Publication date: 26 October 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1509.08123
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- DNF sparsification and a faster deterministic counting algorithm
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
- Reducing the seed length in the Nisan-Wigderson generator
- Exposure-resilient extractors and the derandomization of probabilistic sublinear time
- Decoding of Reed Solomon codes beyond the error-correction bound
- On construction of \(k\)-wise independent random variables
- On a set of almost deterministic k-independent random variables
- Random sampling and approximation of MAX-CSPs
- Efficient learning algorithms yield circuit lower bounds
- Pseudorandom Generators for Polynomial Threshold Functions
- A Deterministic Algorithm for the Frieze–Kannan Regularity Lemma
- A Sample of Samplers: A Computational Perspective on Sampling
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Property testing and its connection to learning and approximation
- Pseudorandom Generators for Regular Branching Programs
- An optimal minimum spanning tree algorithm
- Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
- On the power of unique 2-prover 1-round games
- Simple Constructions of Almost k-wise Independent Random Variables
- Addendum to “simple constructions of almost k-wise independent random variables”
- The Algorithmic Aspects of the Regularity Lemma
- A randomized linear-time algorithm to find minimum spanning trees
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- MAX-CUT has a randomized approximation scheme in dense graphs
- A fast new algorithm for weak graph regularity
- Pseudorandomness from Shrinkage
- Approximating Dense Max 2-CSPs
- An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions
- On Regularity Lemmas and their Algorithmic Applications
- Algorithms and Data Structures
- Pseudorandom generators without the XOR lemma
