- author = "Andre Gronemeier",
- title = "Approximating {Boolean} Functions by {OBDDs}",
- booktitle = "29th Symposium on Mathematical Foundations of Computer Science MFCS 2004",
- year = "2004",
- editor = "Jir\'{\i} Fiala and V{\'a}clav Koubek and Jan Kratochv\'{\i}l",
- series = "Lecture Notes in Computer Science",
- volume = "3153",
- pages = "251--262",
- address = "Prague, Czech Republic",
- month = aug # " 22-27",
- publisher = "Springer",
- bibsource = "DBLP, http://dblp.uni-trier.de",
- keywords = "genetic algorithms, genetic programming",
- ISBN = "3-540-22823-3",
-
URL = "
http://ls2-www.cs.uni-dortmund.de/~gronemeier/publications/obdd-approx-mfcs.pdf",
-
DOI = "
doi:10.1007/978-3-540-28629-5_17",
- size = "12 pages",
-
abstract = "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 prove the following results on
OBDD approximations of Boolean functions:
1. We show that OBDDs approximating the well-known hidden weighted bit function for uniformly distributed inputs with constant 1/4 error have size 2?(n ) , improving a previously known result.
2. We prove that for every variable order ? the approximation of some output bits of integer multiplication with constant error requires ?-OBDDs of exponential size.",
- notes = "replaced by \cite{Gronemeier:2007:DAM}",
