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 use 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 deΓΏned sequence of boolean functions fn on n variables such that fn has rectangle approximations with a constant number of rectangles and one-sided error 1 3 + o(1) or two-sided error 1 4 + o(1), but, on the other hand, fn requires exponentially many rectangles if the error bounds are decreased by an arbitrarily small constant.
As applications of this result, the following separation results for read-once branching programs are obtained. The functions from the main result require only linear size for nondeterministic read-once branching programs and randomized read-once branching programs with two-sided error 1 3 +o(1), while randomized read-once branching programs with constant two-sided error smaller than 1 3 and unambiguous nondeterministic read-once branching programs require exponential size.