Approximating Boolean functions by OBDDs
type: Item
instance of: scholarly article
title: Approximating Boolean functions by OBDDs
zbMATH Open document ID: 1178.68257
author: André Gronemeier
published in: Discrete Applied Mathematics
publication date: 2007-02-19T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 5128023
zbMATH Keywords: OBDD
zbMATH Keywords: communication complexity
zbMATH Keywords: approximation
MaRDI profile type: Publication
full work available at URL: j.dam.2006.04.037
OpenAlex ID: W2048763879
cites work: A lower bound for integer multiplication on randomized ordered read-once branching programs.
cites work: On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
cites work: On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
cites work: Read-once projections and formal circuit verification with binary decision diagrams
cites work: A read-once branching program lower bound of Ω(2 n/4 ) for integer multiplication using universal hashing
cites work: Graph-Based Algorithms for Boolean Function Manipulation
cites work: On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
cites work: A Reliable Randomized Algorithm for the Closest-Pair Problem
cites work: Q4234109
cites work: Communication Complexity
cites work: Q4234058
cites work: Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
cites work: Q4855565
cites work: Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
cites work: Branching Programs and Binary Decision Diagrams
cites work: Q2762533
DOI: 10.1016/J.DAM.2006.04.037
Recommended article: Mathematical Foundations of Computer Science 2004
Recommended article: On the OBDD-representation of general Boolean functions
Recommended article: On approximation by \(^{\oplus}\)-OBDDs
Recommended article: Optimal bounds for the approximation of Boolean functions and some applications
Recommended article: Optimal bounds on the approximation of boolean functions with consequences on the concept of hardness
Recommended article: On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
Recommended article: Approximating Boolean Functions with Depth-2 Circuits
Recommended article: Computations in Boolean Algebra with Approximation
Recommended article: Boolean algebra approximations
Recommended article: Asymptotically optimal Boolean functions
description: scientific article; zbMATH DE number 5128023