Approximating Boolean functions by OBDD

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

  author =       "Andre Gronemeier",
  title =        "Approximating {Boolean} functions by OBDD",
  journal =      "Discrete Applied Mathematics",
  year =         "2007",
  volume =       "155",
  number =       "2",
  pages =        "194--209",
  month =        "15 " # jan,
  note =         "29th Symposium on Mathematical Foundations of Computer
                 Science MFCS 2004",
  keywords =     "genetic algorithms, genetic programming, OBDD,
                 Communication complexity, Approximation",
  DOI =          "doi:10.1016/j.dam.2006.04.037",
  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 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.",
  notes =        "replaces \cite{DBLP:conf/mfcs/Gronemeier04}",

Genetic Programming entries for Andre Gronemeier