• DocumentCode
    1780761
  • Title

    A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length

  • Author

    Kane, D.M.

  • Author_Institution
    Dept. of Math., Stanford Univ., Stanford, CA, USA
  • fYear
    2014
  • fDate
    11-13 June 2014
  • Firstpage
    217
  • Lastpage
    228
  • Abstract
    We develop and analyze a new family of pseudorandom generators for polynomial threshold functions with respect to the Gaussian distribution. In particular, for any fixed degree we develop a generator whose seed length is subpolynomial in the error parameter, ε. We get particularly nice results for degree 1 and degree 2 threshold functions, in which cases our seed length is O(log(n) + log3/2(1/ε)) and exp(O(log2/3(1/ε))), respectively.
  • Keywords
    Gaussian distribution; computational complexity; random number generation; Gaussian distribution; degree 1 threshold functions; degree 2 threshold functions; error parameter; polynomial threshold functions; pseudorandom generator; subpolynomial seed length; Approximation methods; Gaussian distribution; Generators; Jacobian matrices; Polynomials; Random variables; Standards; Polynomial threshold function; Pseudorandom generator;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity (CCC), 2014 IEEE 29th Conference on
  • Conference_Location
    Vancouver, BC
  • Type

    conf

  • DOI
    10.1109/CCC.2014.30
  • Filename
    6875491
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1780761