On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
We consider the problem of fixed-polynomial lower bounds on the size of arithmetic circuits computing uniform families of polynomials. Assuming the generalised Riemann hypothesis (GRH), we show that for all k , there exist polynomials with coefficients in MA MA having no arithmetic circuits of size O(nk) O ( n k ) over C C (allowing any complex constant). We also build a family of polynomials that can be evaluated in AM AM having no arithmetic circuits of size O(nk) O ( n k ) . Then we investigate the link between fixed-polynomial size circuit bounds in the Boolean and arithmetic settings. In characteristic zero, it is proved that NP?size(nk) NP ? size ( n k ) , or MA?size(nk) MA ? size ( n k ) , or NP=MA NP = MA imply lower bounds on the circuit size of uniform polynomials in n  variables from the class VNP VNP over C C , assuming GRH. In positive characteristic p , uniform polynomials in VNP VNP have circuits of fixed-polynomial size if and only if both VP=VNP VP = VNP over Fp F p and ModpP Mod p P has circuits of fixed-polynomial size.
circuit lower bounds arithmetic circuits valiant's classes complex field arthurmerlin