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.