Result: Approximating boolean functions by OBDDs
Title:
Approximating boolean functions by OBDDs
Authors:
Source:
29th symposium on mathematical foundations of computer science MFCS 2004Discrete applied mathematics. 155(2):194-209
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 22 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Ordre, treillis, structures algébriques ordonnées, Order, lattices, ordered algebraic structures, Sciences appliquees, Applied sciences, Telecommunications et theorie de l'information, Telecommunications and information theory, Théorie de l'information, du signal et des communications, Information, signal and communications theory, Théorie du signal et des communications, Signal and communications theory, Approximation fonction, Function approximation, Borne inférieure, Lower bound, Cota inferior, Complexité communication, Communication complexity, Fonction booléenne, Boolean function, Función booliana, Fonction poids, Weight function, Función peso, Multiplication, Multiplicación, Théorie programmation, Programming theory, Approximation pondérée, OBDD, Théorie apprentissage, Approximation
Document Type:
Conference
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Lehrstuhl Informatik 2, Universität Dortmund, Germany
ISSN:
0166-218X
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Mathematics
Telecommunications and information theory
Telecommunications and information theory
Accession Number:
edscal.18454954
Database:
PASCAL Archive
Further Information
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.