
A Geometric Bridge from Convex Polytopes to
Threshold Logic
 M. Reza EmamyK.
abstract

A cutcomplex is a cubical complex whose vertices are strictly separable
from the rest of the vertices of the ncube by a hyperplane of Rn. These ob
jects manifest geometric presentations for threshold Boolean functions, the
fundamental elements of study in threshold logic. Geometric view points in
threshold logic were proposed by J. P. Roth and then by S. T. Hu more than
fifty years ago. Recently, guided by a conjecture of MetropolisRota, we have
shown that the rotating hyperplane methods are useful in the characteriza
tion of the cutcomplexes with few maximal faces. Here, we show that the
rotating hyperplanes could play a basic role in study of convex polytopes
and so the latter techniques can also make a bridge from convex polytopes
to threshold logic. Finally, we show that geometric characterization of cut
complexes is also closely related to the complexity of a greedy algorithm in
optimization of a class of threshold pseudoBoolean functions.

