Fourier bounds and pseudorandom generators for product tests
From MaRDI portal
Publication:5091757
DOI10.4230/LIPIcs.CCC.2019.7OpenAlexW2963998457MaRDI QIDQ5091757
Publication date: 27 July 2022
Full work available at URL: https://arxiv.org/abs/1902.02428
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudorandom generators for combinatorial checkerboards
- Randomness buys depth for approximate counting
- On approximate majority and probabilistic time
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Convex functions, partial orderings, and statistical applications
- Pseudorandom generators for space-bounded computation
- Improved algorithms via approximations of probability distributions
- A polynomial bound in Freiman's theorem.
- Improved pseudorandom generators for combinatorial rectangles
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- Randomness is linear in space
- How much are increasing sets positively correlated?
- Quantitative relation between noise sensitivity and influences
- On the Fourier tails of bounded functions over the discrete cube
- Pseudorandomness for network algorithms
- Pseudorandomness for Regular Branching Programs via Fourier Analysis
- BQP and the polynomial hierarchy
- Two Sides of the Coin Problem
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Short monotone formulae for the majority function
- Improved Pseudorandom Generators for Depth 2 Circuits
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- Pseudorandomness via the Discrete Fourier Transform
- Bounded Independence Plus Noise Fools Products
- Efficient approximation of product distributions
- The Coin Problem for Product Tests
- An Entropic Proof of Chang's Inequality
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
- Analysis of Boolean Functions
- Pseudorandom generators for width-3 branching programs
- Improved pseudorandomness for unordered branching programs through local monotonicity
- Pseudorandomness from Shrinkage
- Hardness Amplification Proofs Require Majority
- Pseudorandomness for Read-Once Formulas
This page was built for publication: Fourier bounds and pseudorandom generators for product tests
