2026-07-20T14:47:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7514 2024-03-12T11:58:29Z ddc:004 open_access

An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields Kumar, Mrinal Saptharishi, Ramprasad arithmetic circuits lower bounds separations depth reduction In this paper, we show exponential lower bounds for the class of homogeneous depth-5 circuits over all small finite fields. More formally, we show that there is an explicit family {P_d} of polynomials in VNP, where P_d is of degree d in n = d^{O(1)} variables, such that over all finite fields GF(q), any homogeneous depth-5 circuit which computes P_d must have size at least exp(Omega_q(sqrt{d})). To the best of our knowledge, this is the first super-polynomial lower bound for this class for any non-binary field. Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-4 circuits [Gupta et al., Fournier et al., Kayal et al., Kumar-Saraf] and for non-homogeneous depth-3 circuits over finite fields [Grigoriev-Karpinski, Grigoriev-Razborov]. Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from GF(q)^n to GF(q) as opposed to looking at them as a space of formal polynomials and builds over a tighter analysis of the lower bound of Kumar and Saraf [Kumar-Saraf]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mrinal Kumar and Ramprasad Saptharishi 2017 Is Part Of LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2017.31 urn:nbn:de:0030-drops-75142 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.31 eng https://creativecommons.org/licenses/by/3.0/legalcode