2026-08-16T20:47:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8886 2024-03-06T10:42:49Z ddc:004 open_access

A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n Kane, Daniel Rao, Sankeerth Pseudorandomness Polynomial Threshold Functions We construct and analyze a pseudorandom generator for degree 2 boolean polynomial threshold functions. Random constructions achieve the optimal seed length of O(log n + log 1/epsilon), however the best known explicit construction of [Ilias Diakonikolas, 2010] uses a seed length of O(log n * epsilon^{-8}). In this work we give an explicit construction that uses a seed length of O(log n + (1/epsilon)^{o(1)}). Note that this improves the seed length substantially and that the dependence on the error epsilon is additive and only grows subpolynomially as opposed to the previously known multiplicative polynomial dependence. Our generator uses dimensionality reduction on a Nisan-Wigderson based pseudorandom generator given by Lu, Kabanets [Kabanets and Lu, 2018]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Kane and Sankeerth Rao 2018 Is Part Of LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2018.2 urn:nbn:de:0030-drops-88861 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.2 eng https://creativecommons.org/licenses/by/3.0/legalcode