Paraunitary matrices, entropy, algebraic condition number and Fourier computation Abstract   The Fourier Transform is one of the most important linear transformations used in science and engineering. Cooley and Tukeyu0027s Fast Fourier Transform (FFT) from 1964 is a method for computing this transformation in time    O  (  n  log  xe2x81xa1  n  )   . From a lower bound perspective, relatively little is known. Ailon shows in 2013 an    xcexa9  (  n  log  xe2x81xa1  n  )    bound for computing the normalized Fourier Transform assuming only unitary operations on two coordinates are allowed at each step, and no extra memory is allowed. In 2014, Ailon then improved the result to show that, in a xcexbawell conditioned computation, Fourier computation can be sped up by no more than    O  (  xcexba  )   . The main conjecture is that Ailonu0027s result can be exponentially improved, in the sense that xcexbawell condition cannot admit    xcfx89  (  log  xe2x81xa1  xcexba  )    speedup.  The main result here is that xe2x80x98algebraicxe2x80x99 xcexbawell condition cannot admit    xcfx89  (    xcexba    )    speedup. One equivalent definition of algebraic condition number is related to the degree of polynomials naturally arising as the computation evolves. Using the maximum modulus theorem from complex analysis, we show that algebraic condition number upper bounds standard condition number, and equals it in certain cases. Algebraic condition number is an interesting measure of numerical computation stability in its own right, and provides a novel computational lens. Moreover, based on evidence from other recent related work, we believe that the approach of algebraic condition number has a good chance of establishing an algebraic version of the main conjecture.

Lower Bounds for Arithmetic Circuits via the Hankel Matrix We study the complexity of representing polynomials by arithmetic circuits in both the commutative and the noncommutative settings. To analyse circuits we count their number of parse trees, which describe the nonassociative computations realised by the circuit. In the noncommutative setting a circuit computing a polynomial of degree d has at most 2O(d) parse trees. Previous superpolynomial lower bounds were known for circuits with up to 2d13e parse trees, for any eu003e0. Our main result is to reduce the gap by showing a superpolynomial lower bound for circuits with just a small defect in the exponent for the total number of parse trees, that is 2d1e, for any eu003e0. In the commutative setting a circuit computing a polynomial of degree d has at most 2O(d log d) parse trees.  We show a superpolynomial lower bound for circuits with up to 2d13e parse trees, for any eu003e0. When d is polylogarithmic in n, we push this further to up to 2d1e parse trees. While these two main results hold in the associative setting, our approach goes through a precise understanding of the more restricted setting where multiplication is not associative, meaning that we distinguish the polynomials (xy)z and x(yz). Our first and main conceptual result is a characterization result: we show that the size of the smallest circuit computing a given nonassociative polynomial is exactly the rank of a matrix constructed from the polynomial and called the Hankel matrix. This result applies to the class of all circuits in both commutative and noncommutative settings, and can be seen as an extension of the seminal result of Nisan giving a similar characterization for noncommutative algebraic branching programs. Our key technical contribution is to provide generic lower bound theorems based on analyzing and decomposing the Hankel matrix, from which we derive the results mentioned above. The study of the Hankel matrix also provides a unifying approach for proving lower bounds for polynomials in the (classical) associative setting.  We demonstrate this by giving alternative proofs of recent lower bounds as corollaries of our generic lower bound results.