An exponential lower bound for homogeneous depth-5 circuits over finite fields

2015/07/01 by Mrinal Kumar, Kumar, Mrinal, Ramprasad Saptharishi +1
Computer Science · #Advanced Graph Theory Research #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #I.1.1 #cs.CC

paper · pdf · doi:10.48550/arxiv.1507.00177

arxiv created 2015/07/01 · openalex publication_date 2015/07/01 · arxiv updated 2015/07/02 · openalex created_date 2016/11/04 · openalex updated_date 2026/07/28

Abstract

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 : d ∈ ℕ\ of polynomials in VNP, where P_d is of degree d in n = d^O(1) variables, such that over all finite fields \mathbbF_q, any homogeneous depth-5 circuit which computes P_d must have size at least exp(Ω_q(√(d))). To the best of our knowledge, this is the first super-polynomial lower bound for this class for any field \mathbbF_q ≠ \mathbbF₂. Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-4 circuits [GKKS13, FLMS13, KLSS14, KS14] and for non-homogeneous depth-3 circuits over finite fields [GK98, GR00]. Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from \mathbbF_qⁿ → \mathbbF_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 [KS14].

Related

• Improved bounds for reduction to depth 4 and depth 3
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
• On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields
• On the power of homogeneous depth 4 arithmetic circuits
• Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits