Approximating Boolean Functions by OBDDs

Created by W.Langdon from gp-bibliography.bib Revision:1.4192

  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,",
  keywords =     "genetic algorithms, genetic programming",
  ISBN =         "3-540-22823-3",
  URL =          "",
  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}",

Genetic Programming entries for Andre Gronemeier