A Small PRG for Polynomial Threshold Functions of Gaussians

DOI10.1109/FOCS.2011.16MaRDI QIDQ5494970zbMATH OpenOpenAlexFDO

Authors Daniel M. Kane

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2011.16

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Cited in

(5)

• A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
• Pseudorandomness via the discrete Fourier transform
• The correct exponent for the Gotsman-Linial conjecture
• Fooling Polytopes
• Simple and efficient pseudorandom generators from gaussian processes

This page was built for publication: A Small PRG for Polynomial Threshold Functions of Gaussians

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