Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions

DOI10.1145/780542.780571zbMath1192.68332OpenAlexW1989110033MaRDI QIDQ3581269

Martin Sauerhoff, Philipp Woelfel

Publication date: 16 August 2010

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

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

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 ⋮ Randomized OBDDs for the most significant bit of multiplication need exponential space ⋮ 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 ⋮ On perfect hashing of numbers with sparse digit representation via multiplication by a constant ⋮ Larger Lower Bounds on the OBDD Complexity of Integer Multiplication ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ Bounds on the OBDD-size of integer multiplication via universal hashing

This page was built for publication: Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions