On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication

DOI10.1109/12.73590zbMath1220.68060OpenAlexW2108016168MaRDI QIDQ3417010

Randal E. Bryant

Publication date: 9 January 2007

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/12.73590

zbMATH Keywords

complexitycomputational complexityBoolean functionslower boundsVLSI implementationsspeedinteger multiplicationgraph representationsdata structurearea-time complexityordered binary decision diagramchip areadigital arithmetic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (68)

Ordered binary decision diagrams and the Shannon effect ⋮ Bounded model checking of infinite state systems ⋮ Better upper bounds on the QOBDD size of integer multiplication ⋮ On the computational power of linearly transformed BDDs ⋮ On the Complexity of the Hidden Weighted Bit Function for Various BDD Models ⋮ Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs ⋮ Efficient data structures for Boolean functions ⋮ Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice ⋮ Binary Decision Diagrams ⋮ On the second-order nonlinearity of the hidden weighted bit function ⋮ Approximating Boolean functions by OBDDs ⋮ Knowledge compilation meets database theory: compiling queries to decision diagrams ⋮ Ordered Binary Decision Diagrams and the Davis-Putnam procedure ⋮ Size of ordered binary decision diagrams representing threshold functions ⋮ Cryptographic properties of the hidden weighted bit function ⋮ On the OBDD Complexity of the Most Significant Bit of Integer Multiplication ⋮ The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions ⋮ A View from the Engine Room: Computational Support for Symbolic Model Checking ⋮ Inferring Congruence Equations Using SAT ⋮ Randomized OBDDs for the most significant bit of multiplication need exponential space ⋮ New results on the most significant bit of integer multiplication ⋮ On the OBDD complexity of the most significant bit of integer multiplication ⋮ Resolution and binary decision diagrams cannot simulate each other polynomially ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ Shared Ordered Binary Decision Diagrams for Dempster-Shafer Theory ⋮ Priority functions for the approximation of the metric TSP ⋮ A lower bound for integer multiplication on randomized ordered read-once branching programs. ⋮ BDDs -- design, analysis, complexity, and applications. ⋮ On efficient implicit OBDD-based algorithms for maximal matchings ⋮ Concatenations of the hidden weighted bit function and their cryptographic properties ⋮ First-order temporal logic monitoring with BDDs ⋮ Bounded semantics ⋮ Strong planning under partial observability ⋮ Graph driven BDDs -- a new data structure for Boolean functions ⋮ OKFDDs versus OBDDs and OFDDs ⋮ Symbolic model checking: \(10^{20}\) states and beyond ⋮ Probabilistic verification of Boolean functions ⋮ On the computational power of binary decision diagram with redundant variables. ⋮ Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems ⋮ Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication ⋮ New lower bounds and hierarchy results for restricted branching programs ⋮ Larger lower bounds on the OBDD complexity of integer multiplication ⋮ A note on the size of OBDDs for the graph of integer multiplication ⋮ Size of OBDD representation of 2-level redundancies functions ⋮ Lower Bounds for Syntactically Multilinear Algebraic Branching Programs ⋮ Lower bounds for restricted read-once parity branching programs ⋮ Embedded software verification using symbolic execution and uninterpreted functions ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ On the descriptive and algorithmic power of parity ordered binary decision diagrams ⋮ On the relation between structured \(d\)-DNNFs and SDDs ⋮ Larger Lower Bounds on the OBDD Complexity of Integer Multiplication ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size ⋮ Solving Quantified Bit-Vector Formulas Using Binary Decision Diagrams ⋮ On the relative succinctness of sentential decision diagrams ⋮ Transparency order for Boolean functions: analysis and construction ⋮ On limitations of structured (deterministic) DNNFs ⋮ Connecting knowledge compilation classes and width parameters ⋮ On the relation between BDDs and FDDs ⋮ Symbolic Reachability for Process Algebras with Recursive Data Types ⋮ EVOLVING INDUCTIVE GENERALIZATION VIA GENETIC SELF-ASSEMBLY ⋮ Bounds on the OBDD-size of integer multiplication via universal hashing ⋮ On the descriptive and algorithmic power of parity ordered binary decision diagrams ⋮ The nonapproximability of OBDD minimization ⋮ A construction of Boolean functions with good cryptographic properties ⋮ Ordered binary decision diagrams as knowledge-bases ⋮ Linear codes are hard for oblivious read-once parity branching programs ⋮ Lower bounds for linearly transformed OBDDs and FBDDs ⋮ Conformant planning via symbolic model checking and heuristic search

This page was built for publication: On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication