Specifying a positive threshold function via extremal points

MaRDI QIDQ4645645zbMATH OpenFDO

Authors Igor Razgon, Victor Zamaraev, Elena Zamaraeva, Vadim Lozin, N. Yu. Zolotykh

Publication date 10 January 2019

Full work available at URL https://arxiv.org/abs/1706.01747, http://proceedings.mlr.press/v76/lozin17a.html

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Abstract: An extremal point of a positive threshold Boolean function $f$ is either a maximal zero or a minimal one. It is known that if $f$ depends on all its variables, then the set of its extremal points completely specifies $f$ within the universe of threshold functions. However, in some cases, $f$ can be specified by a smaller set. The minimum number of points in such a set is the specification number of $f$. It was shown in [S.-T. Hu. Threshold Logic, 1965] that the specification number of a threshold function of $n$ variables is at least $n+1$. In [M. Anthony, G. Brightwell, and J. Shawe-Taylor. On specifying Boolean functions by labelled examples. Discrete Applied Mathematics, 1995] it was proved that this bound is attained for nested functions and conjectured that for all other threshold functions the specification number is strictly greater than $n+1$. In the present paper, we resolve this conjecture negatively by exhibiting threshold Boolean functions of $n$ variables, which are non-nested and for which the specification number is $n+1$. On the other hand, we show that the set of extremal points satisfies the statement of the conjecture, i.e., a positive threshold Boolean function depending on all its $n$ variables has $n+1$ extremal points if and only if it is nested. To prove this, we reveal an underlying structure of the set of extremal points.

Recommendations

• On the constructive characterization of threshold functions
• The extreme points of a class of functions with positive real part
• The extreme points of a class of functions with positive real part
• A functional extremal criterion
• Extremal properties of polynomial threshold functions
• scientific article; zbMATH DE number 1225796
• On an extremal problem for positive definite functions
• On the number of threshold functions
• Una generalizacion de la caracterizacion de puntos extremos
• Threshold functions

Cited in

(4)

• Linear read-once and related Boolean functions
• On accumulation points of pseudo-effective thresholds
• On Boolean threshold functions with minimum specification number
• A characterization of 2-threshold functions via pairs of prime segments

This page was built for publication: Specifying a positive threshold function via extremal points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645645)