Specifying a positive threshold function via extremal points

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v76-lozin17a, title = {Specifying a positive threshold function via extremal points}, author = {Lozin, Vadim and Razgon, Igor and Zamaraev, Viktor and Zamaraeva, Elena and Zolotykh, Nikolai Yu.}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {208--222}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/lozin17a/lozin17a.pdf}, url = {https://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.} }
Endnote
%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 %P 208--222 %U https://proceedings.mlr.press/v76/lozin17a.html %V 76 %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.
APA
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 Proceedings of Machine Learning Research 76:208-222 Available from https://proceedings.mlr.press/v76/lozin17a.html.

Related Material