Finite tensor savings and exact Fourier circuits
In the unrestricted nonuniform complex linear-circuit model, ; equivalently, for every and every integer , there is an integer and an exact circuit for with fewer than gates.
The headline claim follows directly from Proposition 3.4 and Theorem 8.3, both of which are rigorously proved in the manuscript.
“Theorem 1.1. In this model, lim inf_{n->infty} L(n) / (n log_2 n) = 0. Equivalently, for every c > 0 and every integer N_0 >= 2, there is an integer n >= N_0 and an exact circuit for F_n with fewer than cn log_2 n gates.” · Show in paper