A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian\n Setting

2014/04/03 by Daniel M. Kane, Kane, Daniel M.
Computer Science · #60G15 #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #G.3 #Numerical Methods and Algorithms #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1404.1103

openalex publication_date 2014/04/03 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

We devise a new pseudorandom generator against degree 2 polynomial threshold\nfunctions in the Gaussian setting. We manage to achieve \ε error with\nseed length polylogarithmic in \ε and the dimension, and exponential\nimprovement over previous constructions.\n

Related

• A Small PRG for Polynomial Threshold Functions of Gaussians
• A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length
• A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
• Pseudorandom Generators for Polynomial Threshold Functions
• Random restrictions and PRGs for PTFs in Gaussian Space