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

@InProceedings{DBLP:conf/mfcs/Gronemeier04, 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}", }

Genetic Programming entries for Andre Gronemeier