A polylogarithmic PRG for degree 2 threshold functions in the Gaussian setting

DOI10.4230/LIPICS.CCC.2015.567MaRDI QIDQ4601847zbMATH OpenFDO

Authors Daniel M. Kane

Publication date 24 January 2018

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

zbMATH Keywords

Gaussian distributionpolynomial threshold functionpseudorandom generator

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• scientific article; zbMATH DE number 7250142
• Pseudorandom generators for low degree polynomials
• Pseudorandom bits for polynomials

Cited in

(5)

• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• Simple and efficient pseudorandom generators from gaussian processes
• scientific article; zbMATH DE number 7250142 (Why is no real title available?)
• The computational advantage of MIP* vanishes in the presence of noise
• The computational advantage of MIP* vanishes in the presence of noise

This page was built for publication: A polylogarithmic PRG for degree 2 threshold functions in the Gaussian setting

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