Efficient monotone circuits for threshold functions

Abstract

Let x = (x ,,.. ., xn), y = (yt ,..., y,) E (0, l}“. constant k. He has shown that the function TL We use the canonical ordering, i.e. x G y iff x, < y, can be computed by a monotone circuit of size for all i. A Boolean function f : (0, l}” --) (0, l}” nk + o(n). The question whether this is the best is called monotone iff x < y implies f(x) < f( y ). result possible remains open (see [9]). Denote by T:(x) the threshold-k-function such that 7”(x,, . . . , x,,)=l iff xi+ *.a +x,>k. Denote by S”(x) the sorting function S”(x) = (T;(X), . . . , T,“(x)), x E (0, I}“. The only symmetric and monotone functions f: (0, I>” --) (0, I} are the threshold functions. The sorting function computes all nontrivial threshold functions. The aim of this note is to give a very simple construction of a monotone circuit of size O(n log k) and depth O(log n) which computes the function TF. Our circuit, based on the AKS circuit, is a natural extension of the result of [l] and an improvement of the result of [3].

Topics

    0 Figures and Tables

      Download Full PDF Version (Non-Commercial Use)