A Geometric Bridge from Convex Polytopes to Threshold Logic
      - 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.