Approximating Boolean functions by OBDD

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

@Article{Gronemeier:2007:DAM,

• 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

Citations