Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426419 | Information and Computation | 2015 | 11 Pages |
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 MAMA having no arithmetic circuits of size O(nk)O(nk) over CC (allowing any complex constant). We also build a family of polynomials that can be evaluated in AMAM having no arithmetic circuits of size O(nk)O(nk). 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(nk), or MA⊂size(nk)MA⊂size(nk), or NP=MANP=MA imply lower bounds on the circuit size of uniform polynomials in n variables from the class VNPVNP over CC, assuming GRH. In positive characteristic p , uniform polynomials in VNPVNP have circuits of fixed-polynomial size if and only if both VP=VNPVP=VNP over FpFp and ModpPModpP has circuits of fixed-polynomial size.