A simple proof of Bazzi's theorem

DOI10.1145/1490270.1490273zbMATH Open1322.68108OpenAlexW2109322425MaRDI QIDQ2947540FDOQ2947540

Authors: Alexander Razborov 

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1490270.1490273

Recommendations

• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• Polylogarithmic independence can fool DNF formulas
• Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)
• Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
• scientific article; zbMATH DE number 6861917

zbMATH Keywords

DNFpseudo-random generators

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Cited In (16)

• Pseudorandom generators for combinatorial checkerboards
• A simple proof of the Bieberbach conjecture
• Bounded-depth circuits cannot sample good codes
• Paradigms for Unconditional Pseudorandom Generators
• A simple proof of a theorem of Bollobás and Leader
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The work of Mark Braverman
• DNF sparsification and a faster deterministic counting algorithm
• Bounded independence plus noise fools products
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• Fooling Polytopes
• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• Bounded indistinguishability and the complexity of recovering secrets
• Small-bias is not enough to hit read-once CNF

This page was built for publication: A simple proof of Bazzi's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947540)