%0 Journal Article %1 Gronemeier:2007:DAM %A Gronemeier, Andre %D 2007 %J Discrete Applied Mathematics %K Approximation Communication OBDD, algorithms, complexity, genetic programming, %N 2 %P 194--209 %R doi:10.1016/j.dam.2006.04.037 %T Approximating Boolean functions by OBDD %V 155 %X 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.

@article{Gronemeier:2007:DAM, 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.}, added-at = {2008-06-19T17:35:00.000+0200}, author = {Gronemeier, Andre}, biburl = {https://www.bibsonomy.org/bibtex/2b433afe1fb9477904e2259afa5589c44/brazovayeye}, doi = {doi:10.1016/j.dam.2006.04.037}, interhash = {9f007b43dca1dae02f6207a12ec6e069}, intrahash = {b433afe1fb9477904e2259afa5589c44}, journal = {Discrete Applied Mathematics}, keywords = {Approximation Communication OBDD, algorithms, complexity, genetic programming,}, month = {15 January}, note = {29th Symposium on Mathematical Foundations of Computer Science MFCS 2004}, notes = {replaces \cite{DBLP:conf/mfcs/Gronemeier04}}, number = 2, pages = {194--209}, timestamp = {2008-06-19T17:40:40.000+0200}, title = {Approximating Boolean functions by {OBDD}}, volume = 155, year = 2007 }