A read-once branching program lower bound of (2ⁿ/4) for integer multiplication using universal hashing

DOI10.1145/380752.380835MaRDI QIDQ5175997zbMATH OpenOpenAlexFDO

Authors Beate Bollig, Philipp Woelfel

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/380752.380835

zbMATH Keywords

computational complexityinteger multiplicationlower boundsread-once branching programs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A Lower Bound for Integer Multiplication with Read-Once Branching Programs
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
• scientific article; zbMATH DE number 1759409
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
• A lower bound for integer multiplication on randomized ordered read-once branching programs.

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(20)

• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• BDDs -- design, analysis, complexity, and applications.
• Better upper bounds on the QOBDD size of integer multiplication
• New results on the most significant bit of integer multiplication
• On the OBDD complexity of the most significant bit of integer multiplication
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
• Randomized OBDDs for the most significant bit of multiplication need exponential size
• On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• A Lower Bound for Integer Multiplication with Read-Once Branching Programs
• scientific article; zbMATH DE number 1263188 (Why is no real title available?)
• scientific article; zbMATH DE number 1759409 (Why is no real title available?)
• Universal Hashing via Integer Arithmetic Without Primes, Revisited
• Streaming and query once space complexity of longest increasing subsequence
• Lower bound proof for the size of BDDs representing a shifted addition
• An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order
• Approximating Boolean functions by OBDDs
• The optimal read-once branching program complexity for the direct storage access function
• A note on the size of OBDDs for the graph of integer multiplication

This page was built for publication: A read-once branching program lower bound of \({\omega}(2^{n/4})\) for integer multiplication using universal hashing

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