On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant

Hervé Fournier, Sylvain Perifel, Rémi de Verclos

Assuming the Generalised Riemann Hypothesis (GRH), we show that for all k, there exist polynomials with coefficients in $\MA$ having no arithmetic circuits of size O(n^k) over the…