Approximating Boolean functions by OBDD
Discrete Applied Mathematics, 155 (2):
194--209 (15 January 2007)29th Symposium on Mathematical Foundations of Computer
Science MFCS 2004.DOI: doi:10.1016/j.dam.2006.04.037
Аннотация
In learning theory and genetic programming, OBDDs are
used to represent approximations of Boolean functions.
This motivates the investigation of the OBDD complexity
of approximating Boolean functions with respect to
given distributions on the inputs. We present a new
type of reduction for one-round communication problems
that is suitable for approximations. Using this new
type of reduction, we improve a known lower bound on
the size of OBDD approximations of the hidden weighted
bit function for uniformly distributed inputs to an
asymptotically tight bound and prove new results about
OBDD approximations of integer multiplication and
squaring for uniformly distributed inputs.