Integer multiplication and the complexity of binary decision diagrams

MaRDI QIDQ3397629zbMATH OpenFDO

Authors Beate Bollig

Publication date 22 September 2009

zbMATH Keywords

complexitydynamic data structureinteger multiplicationordered binary decision diagrams

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the OBDD complexity of 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
• Larger lower bounds on the OBDD complexity of integer multiplication
• New Results on the Most Significant Bit of Integer Multiplication

Cited in

(7)

• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• Randomized OBDDs for the most significant bit of multiplication need exponential space
• When is scalar multiplication decidable?
• Factorization using binary decision diagrams
• Randomized OBDDs for the most significant bit of multiplication need exponential size
• On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
• Larger lower bounds on the OBDD complexity of integer multiplication

This page was built for publication: Integer multiplication and the complexity of binary decision diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3397629)