License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.37
URN: urn:nbn:de:0030-drops-147304
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14730/
Go to the corresponding LIPIcs Volume Portal

Servedio, Rocco A. ; Tan, Li-Yang

Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma

pdf-format:
LIPIcs-APPROX37.pdf (0.9 MB)

Abstract

We study the problem of deterministically approximating the number of satisfying assignments of a polynomial threshold function (PTF) over Boolean space. We present and analyze a scheme for transforming such algorithms for PTFs over Gaussian space into algorithms for the more challenging and more standard setting of Boolean space. Applying this transformation to existing algorithms for Gaussian space leads to new algorithms for Boolean space that improve on prior state-of-the-art results due to Meka and Zuckerman [Meka and Zuckerman, 2013] and Kane [Kane, 2012]. Our approach is based on a bias-preserving derandomization of Meka and Zuckerman’s regularity lemma for polynomials [Meka and Zuckerman, 2013] using the [Rocco A. Servedio and Li-Yang Tan, 2018] pseudorandom generator for PTFs.

BibTeX - Entry

@InProceedings{servedio_et_al:LIPIcs.APPROX/RANDOM.2021.37,
  author =	{Servedio, Rocco A. and Tan, Li-Yang},
  title =	{{Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14730},
  URN =		{urn:nbn:de:0030-drops-147304},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.37},
  annote =	{Keywords: Derandomization, Polynomial threshold functions, deterministic approximate counting}
}

Keywords: Derandomization, Polynomial threshold functions, deterministic approximate counting
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue Date: 2021
Date of publication: 15.09.2021

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