New results on the most significant bit of integer multiplication

DOI10.1007/s00224-009-9238-yzbMath1209.68270OpenAlexW2045680321MaRDI QIDQ2429728

Jochen Klump, Beate Bollig

Publication date: 1 April 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9238-y

zbMATH Keywords

computational complexityupper boundsordered binary decision diagramslower boundsinteger multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Implicit computation of maximum bipartite matchings by sublinear functional operations ⋮ An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Better upper bounds on the QOBDD size of integer multiplication
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
• Bounds on the OBDD-size of integer multiplication via universal hashing
• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• Larger Lower Bounds on the OBDD Complexity of Integer Multiplication
• Graph-Based Algorithms for Boolean Function Manipulation
• A Lower Bound for Integer Multiplication with Read-Once Branching Programs
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• A read-once branching program lower bound of Ω(2 ^n/4 ) for integer multiplication using universal hashing