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

ABSTRACT

We prove exponential size lower bounds for nondeterministic and randomized read-k BPs as well as a time-space tradeoff lower bound for unrestricted, deterministic multi-way BPs computing the middle bit of integer multiplication. The lower bound for randomized read-k BPs is superpolynomial as long as the error probability is superpolynomially small. For polynomially small error, we have a polynomial upper bound on the size of approximating read once BPs for this function. The lower bounds follow from a more general result for the graphs of universal hash classes that is applicable to the graphs of arithmetic functions such as integer multiplication, convolution, and finite field multiplication.

REFERENCES

• 1: F. Ablayev and M. Karpinski. A lower bound for integer multiplication on randomized ordered read-once branching programs. In Proc. of 1st CSIT, Electronic Edition, 1999.
• 2: Miklós Ajtai, Determinism versus non-determinism for linear time RAMs (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.632-641, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301424]
• 3: Miklos Ajtai, A Non-Linear Time Lower Bound for Boolean Branching Programs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.60, October 17-18, 1999
• 4: Paul Beame , T. S. Jayram , Michael Saks, Time-space tradeoffs for branching programs, Journal of Computer and System Sciences, v.63 n.4, p.542-572, December 2001 [doi>10.1006/jcss.2001.1778]
• 5: P. Beame , M. Saks , Xiaodong Sun , E. Vee, Super-linear time-space tradeoff lower bounds for randomized computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.169, November 12-14, 2000
• 6: Paul Beame , Erik Vee, Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510006]
• 7: Beate Bollig, Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication, Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, p.222-231, September 01, 2000
• 8: Beate Bollig , Stephan Waack , Philipp Woelfel, Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.83-94, August 25-30, 2002
• 9: Beate Bollig , Philipp Woelfel, A read-once branching program lower bound of Ω(2^n/4) for integer multiplication using universal hashing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.419-424, July 2001, Hersonissos, Greece [doi>10.1145/380752.380835]
• 10: Beate Bollig , Philipp Woelfel, A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications, Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science, p.131-142, August 26-30, 2002
• 11: A. Borodin and S. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comp., 11(2):287--297, 1982.
• 12: A. Borodin , A. Razborov , R. Smolensky, On lower bounds for read-k-times branching programs, Computational Complexity, v.3 n.1, p.1-18, Jan. 1993 [doi>10.1007/BF01200404]
• 13: Randal E. Bryant, On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication, IEEE Transactions on Computers, v.40 n.2, p.205-213, February 1991 [doi>10.1109/12.73590]
• 14: J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143--154, 1979.
• 15: Martin Dietzfelbinger, Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes, Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, p.569-580, February 22-24, 1996
• 16: Martin Dietzfelbinger , Torben Hagerup , Jyrki Katajainen , Martti Penttonen, A reliable randomized algorithm for the closest-pair problem, Journal of Algorithms, v.25 n.1, p.19-51, Oct. 1997 [doi>10.1006/jagm.1997.0873]
• 17: Jordan Gergov, Time-space tradeoffs for integer multiplication on various types of input oblivious sequential machines, Information Processing Letters, v.51 n.5, p.265-269, Sept. 12, 1994 [doi>10.1016/0020-0190(94)00094-8]
• 18: S. Jukna. The graph of integer multiplication is hard for read-k-times networks. Technical Report 95-10, Universität Trier, 1995. Available under ftp://ftp.informatik.uni-trier.de/pub/Users-Root/reports/95-10.ps.
• 19: Yishay Mansour , Noam Nisan , Prasoon Tiwari, The computational complexity of universal hashing, Theoretical Computer Science, v.107 n.1, p.121-133, Jan. 4, 1993 [doi>10.1016/0304-3975(93)90257-T]
• 20: Stephen Ponzio, A Lower Bound for Integer Multiplication with Read-Once Branching Programs, SIAM Journal on Computing, v.28 n.3, p.798-815, Feb. 1999 [doi>10.1137/S0097539795290349]
• 21: Branching programs and binary decision diagrams: theory and applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 22: M. N. Wegman and J. L. Carter. New classes and applications of hash functions. In Proc. of 20th FOCS, pages 175--182, 1979.
• 23: Philipp Woelfel, Efficient Strongly Universal and Optimally Universal Hashing, Proceedings of the 24th International Symposium on Mathematical Foundations of Computer Science, p.262-272, September 06-10, 1999
• 24: Philipp Woelfel, New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.563-574, February 15-17, 2001
• 25: Philipp Woelfel, On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.80, May 21-24, 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

General Terms:
Theory

Keywords:
branching program, hash class, integer multiplication, lower bound, random access machine, time-space tradeoff