Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
From MaRDI portal
Publication:3581269
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
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