On encoding and enumerating threshold functions

Characterization of Linearly Separable Boolean Functions: A Graph-Theoretic Perspective

In this paper, we present a novel approach for studying Boolean function in a graph-theoretic perspective. In particular, we first transform a Boolean function f of n variables into an induced subgraph H_f of the n -dimensional hypercube, and then, we show the properties of linearly separable Boolean functions on the basis of the analysis of the structure of H_f . We define a new class of graphs, called hyperstar, and prove that the induced subgraph H_f of any linearly separable Boolean function f is a hyperstar. The proposal of hyperstar helps us uncover a number of fundamental properties of linearly separable Boolean functions in this paper.

Separating points by parallel hyperplanes--characterization problem

This paper deals with partitions of a discrete set S of points in a d-dimensional space, by h parallel hyperplanes. Such partitions are in a direct correspondence with multilinear threshold functions which appear in the theory of neural networks and multivalued logic. The characterization (encoding) problem is studied. We show that a unique characterization (encoding) of such multilinear partitions of S = {0, 1,..., m-1}d is possible within theta(h x d2 x log m) bit rate per encoded partition. The proposed characterization (code) consists of (d + 1) x (h + 1) discrete moments having the order no bigger than 1. The obtained bit rate is evaluated depending on the mutual relations between h, d, and m. The optimality is reached in some cases.