Lower bounds on the bounded coefficient complexity of bilinear maps

DOI10.1145/990308.990311zbMATH Open1192.68312arXivcs/0301016OpenAlexW1979175600MaRDI QIDQ3583577FDOQ3583577

Authors: Peter Bürgisser, Martin Lotz 

Publication date: 17 August 2010

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We prove lower bounds of order $nlogn$ for both the problem to multiply polynomials of degree $n$, and to divide polynomials with remainder, in the model of bounded coefficient arithmetic circuits over the complex numbers. These lower bounds are optimal up to order of magnitude. The proof uses a recent idea of R. Raz [Proc. 34th STOC 2002] proposed for matrix multiplication. It reduces the linear problem to multiply a random circulant matrix with a vector to the bilinear problem of cyclic convolution. We treat the arising linear problem by extending J. Morgenstern's bound [J. ACM 20, pp. 305-306, 1973] in a unitarily invariant way. This establishes a new lower bound on the bounded coefficient complexity of linear forms in terms of the singular values of the corresponding matrix. In addition, we extend these lower bounds for linear and bilinear maps to a model of circuits that allows a restricted number of unbounded scalar multiplications.

Full work available at URL: https://arxiv.org/abs/cs/0301016

Recommendations

• Lower bounds for the complexity of polynomials
• STACS 2005
• On the Complexity of Matrix Product
• A lower bound for the multiplication of polynomials modulo a polynomial
• Lower Bounds for Matrix Product

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (7)

• Binary determinantal complexity
• Faster polynomial multiplication via discrete Fourier transforms
• Bounds for semi-disjoint bilinear forms in a unit-cost computational model
• A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle
• Matrix rigidity of random Toeplitz matrices
• Lower bounds for the complexity of polynomials
• Entropy of operators or why matrix multiplication is hard for depth-two circuits

This page was built for publication: Lower bounds on the bounded coefficient complexity of bilinear maps

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