Bounds on the OBDD-size of integer multiplication via universal hashing
From MaRDI portal
Publication:2575837
DOI10.1016/j.jcss.2005.05.004zbMath1082.68021OpenAlexW2073781300MaRDI QIDQ2575837
Publication date: 7 December 2005
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2005.05.004
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 (11)
Better upper bounds on the QOBDD size of integer multiplication ⋮ On the OBDD Complexity of the Most Significant Bit of Integer Multiplication ⋮ Randomized OBDDs for the most significant bit of multiplication need exponential space ⋮ Representing the integer factorization problem using ordered binary decision diagrams ⋮ New results on the most significant bit of integer multiplication ⋮ On the OBDD complexity of the most significant bit of integer multiplication ⋮ Larger lower bounds on the OBDD complexity of integer multiplication ⋮ A note on the size of OBDDs for the graph of integer multiplication ⋮ An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order ⋮ Larger Lower Bounds on the OBDD Complexity of Integer Multiplication ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the size of binary decision diagrams representing Boolean functions
- The computational complexity of universal hashing
- Universal classes of hash functions
- Reduction of OBDDs in linear time
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
- Graph-Based Algorithms for Boolean Function Manipulation
- A Reliable Randomized Algorithm for the Closest-Pair Problem
- Improving the variable ordering of OBDDs is NP-complete
- Branching Programs and Binary Decision Diagrams
- Universal hashing and k-wise independent random variables via integer arithmetic without primes
This page was built for publication: Bounds on the OBDD-size of integer multiplication via universal hashing