On the limits of depth reduction at depth 3 over small finite fields

We also give an example of an explicit polynomial (NWn,ϵ(X)) in VNP (which is not known to be in VP), for which any ΣΠΣ circuit computing it (over fixed-size fields) must be of size 2Ω(nlog⁡n). The polynomial we consider is constructed from the combinatorial design of Nisan and Wigderson, and is closely related to the polynomials considered in many recent papers (by Kayal-Saha-Saptharishi, Kayal-Limaye-Saha-Srinivasan, and Kumar-Saraf), where strong depth 4 circuit size lower bounds are shown.