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

DOI10.1145/380752.380835zbMath1323.68293OpenAlexW2072295723MaRDI QIDQ5175997

Philipp Woelfel, Beate Bollig

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 complexitylower boundsread-once branching programsinteger multiplication

Mathematics Subject Classification ID

Related Items (13)

Better upper bounds on the QOBDD size of integer multiplication ⋮ Approximating Boolean functions by OBDDs ⋮ On the OBDD Complexity of the Most Significant Bit of Integer Multiplication ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ New results on the most significant bit of integer multiplication ⋮ On the OBDD complexity of the most significant bit of integer multiplication ⋮ BDDs -- design, analysis, complexity, and applications. ⋮ The optimal read-once branching program complexity for the direct storage access function ⋮ Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for 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 ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size

Cites Work

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

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