scientific article; zbMATH DE number 7250141

DOI10.4230/LIPIcs.CCC.2018.1zbMath1441.68149MaRDI QIDQ5121889

Eshan Chattopadhyay, Shachar Lovett, Kaave Hosseini, Pooya Hatami

Publication date: 22 September 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

sensitivityrandom walkspolarizationpseudorandom generatorsbranching program

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (8)

An Optimal Separation of Randomized and Quantum Query Complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Quantum versus randomized communication complexity, with efficient players

Cites Work

• Unnamed Item
• Unnamed Item
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Pseudorandom bits for constant depth circuits
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• Pseudorandomness for Regular Branching Programs via Fourier Analysis
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Constant depth circuits, Fourier transform, and learnability
• Expander graphs and their applications
• Polylogarithmic independence fools AC ⁰ circuits
• Simple Constructions of Almost k-wise Independent Random Variables

This page was built for publication: