Vadim Lozin,
Igor Razgon,
Viktor Zamaraev,
Elena Zamaraeva,
Nikolai Yu. Zolotykh
;
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:208-222, 2017.
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$. Hu (1965) showed that the specification number of a threshold function of $n$ variables is at least $n+1$. Anthony et al. (1995) 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.
@InProceedings{pmlr-v76-lozin17a,
title = {Specifying a positive threshold function via extremal points},
author = {Vadim Lozin and Igor Razgon and Viktor Zamaraev and Elena Zamaraeva and Nikolai Yu. Zolotykh},
booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory},
pages = {208--222},
year = {2017},
editor = {Steve Hanneke and Lev Reyzin},
volume = {76},
series = {Proceedings of Machine Learning Research},
address = {Kyoto University, Kyoto, Japan},
month = {15--17 Oct},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v76/lozin17a/lozin17a.pdf},
url = {http://proceedings.mlr.press/v76/lozin17a.html},
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$. Hu (1965) showed that the specification number of a threshold function of $n$ variables is at least $n+1$. Anthony et al. (1995) 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.}
}
%0 Conference Paper
%T Specifying a positive threshold function via extremal points
%A Vadim Lozin
%A Igor Razgon
%A Viktor Zamaraev
%A Elena Zamaraeva
%A Nikolai Yu. Zolotykh
%B Proceedings of the 28th International Conference on Algorithmic Learning Theory
%C Proceedings of Machine Learning Research
%D 2017
%E Steve Hanneke
%E Lev Reyzin
%F pmlr-v76-lozin17a
%I PMLR
%J Proceedings of Machine Learning Research
%P 208--222
%U http://proceedings.mlr.press
%V 76
%W PMLR
%X 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$. Hu (1965) showed that the specification number of a threshold function of $n$ variables is at least $n+1$. Anthony et al. (1995) 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.
Lozin, V., Razgon, I., Zamaraev, V., Zamaraeva, E. & Zolotykh, N.Y.. (2017). Specifying a positive threshold function via extremal points. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in PMLR 76:208-222
This site last compiled Mon, 09 Apr 2018 09:37:13 +0000
