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

2013/04/22 by Hervé Fournier, Fournier, Hervé, Sylvain Perifel +4
Computer Science · Mathematics · #Advanced Graph Theory Research #Analytic Number Theory Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph theory and applications #Limits and Structures in Graph Theory #cs.CC

paper · pdf · doi:10.48550/arxiv.1304.5910

arxiv created 2013/04/22 · openalex publication_date 2013/04/22 · arxiv updated 2013/04/23 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

Abstract

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 complex field (allowing any complex constant). We also build a family of polynomials that can be evaluated in AM having no arithmetic circuits of size 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 \not⊂ \size(n^k), or \MA ⊂ \size(n^k), or NP=MA imply lower bounds on the circuit size of uniform polynomials in n variables from the class VNP over the complex field, assuming GRH. In positive characteristic p, uniform polynomials in VNP have circuits of fixed-polynomial size if and only if both VP=VNP over F_p and Mod_pP has circuits of fixed-polynomial size.

Related

• Functional lower bounds for restricted arithmetic circuits of depth four
• An exponential lower bound for homogeneous depth-5 circuits over finite fields
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
• New Lower Bounds against Homogeneous Non-Commutative Circuits
• Arithmetic circuits: the chasm at depth four gets wider