License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2018.2
URN: urn:nbn:de:0030-drops-88861
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8886/
Go to the corresponding LIPIcs Volume Portal

Kane, Daniel ; Rao, Sankeerth

A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n

pdf-format:
LIPIcs-CCC-2018-2.pdf (0.6 MB)

Abstract

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].

BibTeX - Entry

@InProceedings{kane_et_al:LIPIcs:2018:8886,
  author =	{Daniel Kane and Sankeerth Rao},
  title =	{{A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{2:1--2:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Rocco A. Servedio},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8886},
  URN =		{urn:nbn:de:0030-drops-88861},
  doi =		{10.4230/LIPIcs.CCC.2018.2},
  annote =	{Keywords: Pseudorandomness, Polynomial Threshold Functions}
}

Keywords: Pseudorandomness, Polynomial Threshold Functions
Collection: 33rd Computational Complexity Conference (CCC 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI