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.ISAAC.2022.52
URN: urn:nbn:de:0030-drops-173372
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17337/
Podolskii, Vladimir ;
Proskurin, Nikolay V.
Polynomial Threshold Functions for Decision Lists
Abstract
For S ⊆ {0,1}ⁿ a Boolean function f : S → {-1,1} is a polynomial threshold function (PTF) of degree d and weight W if there is a polynomial p with integer coefficients of degree d and with sum of absolute coefficients W such that f(x) = sign p(x) for all x ∈ S. We study a representation of decision lists as PTFs over Boolean cubes {0,1}ⁿ and over Hamming balls {0,1}ⁿ_{≤ k}.
As our first result, we show that for all d = O((n/(log n))^{1/3}) any decision list over {0,1}ⁿ can be represented by a PTF of degree d and weight 2^O(n/d²). This improves the result by Klivans and Servedio [Adam R. Klivans and Rocco A. Servedio, 2006] by a log² d factor in the exponent of the weight. Our bound is tight for all d = O((n/(log n))^{1/3}) due to the matching lower bound by Beigel [Richard Beigel, 1994].
For decision lists over a Hamming ball {0,1}ⁿ_{≤ k} we show that the upper bound on weight above can be drastically improved to n^O(√k) for d = Θ(√k). We also show that similar improvement is not possible for smaller degrees by proving the lower bound W = 2^Ω(n/d²) for all d = O(√k).
BibTeX - Entry
@InProceedings{podolskii_et_al:LIPIcs.ISAAC.2022.52,
author = {Podolskii, Vladimir and Proskurin, Nikolay V.},
title = {{Polynomial Threshold Functions for Decision Lists}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {52:1--52:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17337},
URN = {urn:nbn:de:0030-drops-173372},
doi = {10.4230/LIPIcs.ISAAC.2022.52},
annote = {Keywords: Threshold function, decision list, Hamming ball}
}
Keywords: |
|
Threshold function, decision list, Hamming ball |
Collection: |
|
33rd International Symposium on Algorithms and Computation (ISAAC 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
14.12.2022 |