Article ID Journal Published Year Pages File Type
426419 Information and Computation 2015 11 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,