A simple proof of Bazzi's theorem

DOI10.1145/1490270.1490273MaRDI QIDQ2947540zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

DNFpseudo-random generators

Mathematics Subject Classification ID

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

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

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
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• scientific article; zbMATH DE number 7650112 (Why is no real title available?)
• scientific article; zbMATH DE number 763851 (Why is no real title available?)
• DNF sparsification and a faster deterministic counting algorithm
• The work of Mark Braverman
• Bounded independence plus noise fools products
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• Fooling Polytopes
• Bounded indistinguishability and the complexity of recovering secrets
• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• 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)