Creative Commons Attribution 4.0 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: https://drops.dagstuhl.de/opus/volltexte/2021/14730/
Servedio, Rocco A. ; Tan, Li-Yang
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma
| pdf-format: |
|
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 | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 15.09.2021 |
