期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：Approximation, branching programs, Communication complexity, lower bounds, nondeterminism, Randomness
