__
TR00-058 | 1st August 2000 00:00
__

#### Approximation of Boolean Functions by Combinatorial Rectangles

**Abstract:**
This paper deals with the number of monochromatic combinatorial

rectangles required to approximate a Boolean function on a constant

fraction of all inputs, where each rectangle may be defined with

respect to its own partition of the input variables. The main result

of the paper is that the number of rectangles required for the

approximation of Boolean functions in this model is very sensitive to

the allowed error: There is an explicitly defined sequence of functions

f_n: {0,1}^n -> {0,1} such that f_n has rectangle approximations with a

constant number of rectangles and one-sided error 1/3+o(1) or two-sided

error 1/4+2^{-\Omega(n)}, but, on the other hand, f_n requires

exponentially many rectangles if the error bounds are decreased by an

arbitrarily small constant.

Rectangle partitions and rectangle approximations with the same

partition of the input variables for all rectangles have been

thoroughly investigated in communication complexity theory. The

complexity measures where each rectangle may have its own partition are

used as tools for proving lower bounds in branching program theory. As

applications of the main result, two separation results for read-once

branching programs are presented.

First, the relationship between nondeterminism and randomness for

read-once branching programs is investigated. It is shown that the

analogs of the complexity classes NP and BPP defined in terms of

read-once branching program size are incomparable if the error for the

randomized model is bounded by a constant smaller than 1/3. The second

result is that unambiguous nondeterministic read-once branching

programs, i.e., programs with at most one accepting computation path

for each input, for the function f_n from the main result have

exponential size. Together with a linear upper bound on the size for

unrestricted nondeterminism, this implies that the analogs of the

classes UP and NP for read-once branching programs are different.