Fourier bounds and pseudorandom generators for product tests

DOI10.4230/LIPIcs.CCC.2019.7OpenAlexW2963998457MaRDI QIDQ5091757

Chin Ho Lee

Publication date: 27 July 2022

Full work available at URL: https://arxiv.org/abs/1902.02428

zbMATH Keywords

pseudorandom generatorsFourier spectrumproduct testbounded independence plus noise

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item

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