arXiv
Open Access
2011
A Small PRG for Polynomial Threshold Functions of Gaussians
Daniel M. Kane
Abstrak
We develop a pseudo-random generator to fool degree-$d$ polynomial threshold functions with respect to the Gaussian distribution. For $c>0$ any constant, we construct a pseudo-random generator that fools such functions to within $ε$ and has seed length $\log(n) 2^{O(d)} ε^{-4-c}$.
Topik & Kata Kunci
Penulis (1)
D
Daniel M. Kane
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2011
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓