A Geometric Bridge from Convex Polytopes to
- M. Reza Emamy-K.
||A cut-complex is a cubical complex whose vertices are strictly separable
from the rest of the vertices of the n-cube 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 Metropolis-Rota, we have
shown that the rotating hyperplane methods are useful in the characteriza-
tion of the cut-complexes 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 pseudo-Boolean functions.
Last updated: November 7, 2009.