2026-07-23T21:56:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17337 2024-03-06T10:59:29Z ddc:004 open_access

Polynomial Threshold Functions for Decision Lists Podolskii, Vladimir Proskurin, Nikolay V. Threshold function decision list Hamming ball 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vladimir Podolskii and Nikolay V. Proskurin 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.52 urn:nbn:de:0030-drops-173372 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.52 eng https://creativecommons.org/licenses/by/4.0/legalcode