Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of

Functions Over Finite Fields

D. Grigoriev^{1}

Departments of Mathematics and Computer Science The Pennsylvania State University University Park, PA 16802 dima@cse.psu.edu

Alexander A. Razborov^{2}

Steklov Mathematical Institute Gubkina 8, 117966, GSP-1 Moscow, Russia

A depth 3 arithmetic circuit can be viewed as a sum of products of linear functions. We prove an exponential complexity lower bound on depth 3 arithmetic circuits computing some natural symmetric functions over a finite field F. Also, we study the complexity of the functions f : D^{n} → F for subsets D ⊂ F. In particular, we prove an exponential lower bound on the complexity of a depth 3 arithmetic circuit which computes the determinant or the permanent of a matrix considered as functions f : (F^{∗})^{n^{2}} → F.

1Partially supported by NSF Grant CCR-9424358.

2Supported by Russian Basic Research Foundation grant 96-01-01222.

Introduction.

We study depth 3 arithmetic circuits computing a function over a finite field (see (1) in section 1 below). Basically, a depth 3 arithmetic circuit can be viewed as a sum of products of linear functions. Despite this clear structure, it appears to be quite difficult to obtain for them complexity lower bounds. Let us mention that the boolean theory of depth 3 (and even bounded-depth) circuits is much more developed (see e.g., [6], [7], [11], [12], [13], [14], [16]). On the other hand, there were also considered arithmetic bounded-depth circuits over the field GF (2) (see [1] and the further literature there).

It is somewhat easier to obtain exponential complexity lower bounds for depth 3 arithmetic circuits under the assumption that they involve just (homogeneous) linear forms, rather than arbitrary linear functions, by the same token, if products in a circuit contain a bounded number of linear functions (see [3], [10]). A breakthrough for arbitrary depth 3 arithmetic circuits was made in [5] where an exponential complexity lower bound was proved for a circuit computing the determinant in the algebra of polynomials over a finite field.

First, in this paper an exponential complexity lower bound is proved for circuits computing symmetric functions over finite fields (theorem 1 in section 1), in particular, the symmetric functions MOD_{p_{1}} over the field GF (p) for distinct primes p, p_{1}. Thus, a depth 3 arithmetic circuit in section 1 is treated in the algebra of functions over a finite field.

Afterwards in the next sections we study depth 3 arithmetic circuits which compute “quasi-boolean” functions f : D^{n} → F where D ⊂ F. This setting extends the approach of [14] where the boolean case D = {0, 1} was considered. In section 2 we give some basic properties of the algebra of all functions f : D^{n} → F.

In section 3 we introduce a m-communication rank and m-rigid rank of a matrix and relate them (lemma 3).

In section 4 we state that a product of linear functions has only few nonzeroes on D^{n}, provided that this product has a large communication (or thereby, rigid as well) rank (lemma 4). This allows to approximate products of linear functions with large communication ranks from a depth 3 arithmetic circuit by a zero function, and in the sequel to deal only with the products having small communication ranks.

In section 5 we provide an approximation of a function f : D^{n} → F with a small depth 3 arithmetic circuit complexity by means of a function having some special form (theorem 2). This allows in a particular case D = F^{∗} (or more generally when |D| = |F |−1) to provide an approximation by means of a sparse polynomial (lemma 5). Moreover, the support (the set of monomials) of this polynomial lies in a union of few balls (w.r.t. the Hamming metric) each of a small radius.

Continuing this topic in section 6, we prove that if the support of a function f : (F^{∗})^{n} → F has a large coding distance then a lower bound of the complexity of computing f by a depth 3 arithmetic circuit is exponential (theorem 3). As a consequence, we obtain exponential complexity lower bounds for computing the determinant or the permanent of a matrix, treating them as the functions f : (F^{∗})^{n^{2}} → F. Thereby, it gives, in particular, the exponential lower bound for the determinant or the permanent in the algebra of functions f : F^{n^{2}} → F, which strengthens the result of [5].

1 Exponential lower bound for depth 3 arithmetic circuits for symmetric functions over a finite field.

We study depth 3 arithmetic circuits, so representations of a function in the following form:

f = ∑_{1≤i≤N} ∏_{j} L_{ij}  (1)

where L_{ij} = ∑_{1≤ℓ≤n}α_{ij}^{(ℓ)}X_{ℓ} + α_{ij}^{(0)} are linear functions. We fix a prime p, denote

by F = GF (p) a finite field and in this section we consider the identity (1) for functions f : F^{n} → F over the field F. The purpose of this section is to obtain exponential lower bounds on the complexity (in fact, on N) in the representations (1) for quite natural symmetric functions f.

Viewing each element x ∈ F as an integer 0 ≤ x (mod p) ≤ p − 1, one can define for any prime q (similar to [14]) a function MOD_{q} : F^{n} → F as follows:

MOD_{q}(x_{1}, …, x_{n}) = \{ \begin{matrix}1 & if ∑_{1≤i≤n}x_{i} (mod p) ≡ 0 (mod q) \\ 0 & else \end{matrix}

Theorem 1 For the complexity of depth 3 arithmetic circuit (1) representing MOD_{q} (provided q ≠ p) the lower bound N ≥ exp(Ω(\sqrt{n}/ log n)) holds (in case p = 2 one has a stronger bound N ≥ exp(Ω(n))).

Proof. Suppose the contrary. By the rank rk(∏_{j}L_{ij}) we mean the rank of

the matrix of coefficients (α_{ij}^{(ℓ)})_{j,ℓ} of the linear functions {L_{ij}}_{j} without their free terms. Take some threshold r being a real number (for the time being it varies, we’ll specify it later). We treat separately the products ∏_{j}L_{ij} with

the rank greater or less than r, respectively.

1.1 Products with the large rank.

Let rk (∏_{j}L_{ij}) ≥ r. Then the probability P r [x ∈ F^{n} : ∏_{j}L_{ij}(x) ≠ 0] ≤

(\frac{p−1}{p})^{r}.

1.2 Products with the small rank.

Now let rk (∏_{j}L_{ij}) < r. Then the degree deg (∏_{j}L_{ij}) ≤ r(p − 1).

Indeed, express each L_{ij} as a linear combination of (less than r) elements of a basis, thereupon open the parenthesis in the product and use the relation L^{p} = L for any (linear) function L.

Denote by g the sum of all the products ∏_{j}L_{ij} (from (1)) of (small) ranks

less than r.

Then P r[x ∈ F^{n} : (MOD_{q} − g)(x) ≠ 0] ≤ (\frac{p−1}{p})^{r} N. In case p = 2 one can take r = n/2 − \sqrt{n} (see [11])and complete the proof of the theorem. From now on we assume that p ≥ 3.

Consider the boolean cube B^{n} = {0, 1}^{n} ⊂ F^{n}. For any vector c = (c_{1}, …, c_{n}) ∈ F^{n} consider a (shifted) function MOD_{q}^{(c)} : B^{n} → F defined by the formula MOD_{q}^{(c)}(x_{1}, …, x_{n}) = MOD_{q}(x_{1} + c_{1}, …, x_{n} + c_{n}). We call c nondegenerated if at least n/2 of its coordinates c_{1}, …, c_{n} are distinct from p − 1. The number of degenerated vectors c does not exceed

( \begin{matrix}n \\ n \end{matrix} ) (p − 1)^{0} + ( \begin{matrix}n \\ n − 1 \end{matrix} ) (p − 1)^{1} + ⋯ + ( \begin{matrix}n \\ [n/2] \end{matrix} ) (p − 1)^{[n/2]}

< 2^{n−1}(p − 1)^{n/2} ≤ \frac{1}{2}p^{n}, hence P r[c ∈ F^{n} is nondegenerated] > \frac{1}{2}.

Since any point from F^{n} belongs to the same number 2^{n} of the shifted boolean cubes B^{n} + c (for both degenerated and nondegenerated vectors c), we conclude that the expectation over all nondegenerated vectors c ∈ F^{n}

E(P r[x ∈ B^{n} : (MOD_{q}^{(c)} − g^{(c)})(x) ≠ 0]) ≤ 2 (\frac{p − 1}{p})^{r} N

where the function g^{(c)}(x) = g(x+c) : B^{n} → F is represented by a polynomial of the degree less than r(p − 1). Pick out a nondegenerated c ∈ F^{n} for which

P r[x ∈ B^{n} : (MOD_{q}^{(c)} − g^{(c)})(x) ≠ 0] ≤ 2 (\frac{p − 1}{p})^{r} N.  (2)

Let 1 ≤ j_{1} < ⋯ < j_{s} ≤ n be such that 0 ≤ c_{j_{i}} (mod p) ≤ p − 2, 1 ≤ i ≤ s, s ≥ n/2. Substituting zeroes for all ℓ with ℓ ∉ {j_{1}, … j_{s}} into the function MOD_{q}^{(c)}(X_{1}, …, X_{n}), one obtains a function MOD_{q,t} : B^{s} → F for a certain 0 ≤ t < q (recall [14] that MOD_{q,t}(y_{1}, …, y_{s}) = 1 if the number of ones among y_{1}, …, y_{s} ∈ {0, 1} has a residue t (mod q), otherwise MOD_{q,t}(y_{1}, …, y_{s}) = 0). Specifying r = \sqrt{n/ log n} we get a contradiction of (2) with the corollary and lemmas 4,5 from [14], that proves theorem 1.

One can introduce a symmetric function MAJ_{F} : F^{n} → F similar to the customary MAJ : B^{n} → {0, 1} and being universal for all symmetric functions. Namely, MAJ_{F} (x_{1}, …, x_{n}) = 1 if γ_{0} ≤ γ_{1} ≤ ⋯ ≤ γ_{p−1} where γ_{i} equals to the number of i (mod p) among x_{1}, …, x_{n} for 0 ≤ i ≤ p − 1, otherwise MAJ_{F} (x_{1}, …, x_{n}) = 0. One can show (similar to theorem 4 [11]) that any symmetric function f(x_{1}, …, x_{n}) : F^{n} → F could be represented as a F - linear combination of the functions of the form MAJ_{F} (X_{1}, …, X_{n}, η_{1}, …, η_{n(p−1)}) for suitable η_{i} ∈ F, 1 ≤ i ≤ n(p − 1). This entails the following corollary.

Corollary 1 For the complexity of depth 3 arithmetic circuit (1) representing MAJ_{F} the lower bound N ≥ exp(Ω(\sqrt{n}/ log n)) holds.

2 Quasi-boolean functions over finite fields.

In the rest of the paper we deal with the following setting. Let q = p^{λ}, F = GF (q), fix a subset D ⊂ F, for nondegenerality we suppose that |D| ≥ 2. The case D = F was studied in section 1, that is why we shall assume that D ≠ F. A function f : D^{n} → F we call quasi-boolean extending the concept from [14] where D was just {0, 1} (actually one could extend this concept further considering functions, say f : D_{1} ×⋯×D_{n} → F for D_{1}, …, D_{n} ⊂ F, but we restrict overselves with the case D_{1} = ⋯ = D_{n} = D for the sake of simplicity of notations). One could also view f as a partial function on the entire space F^{n}.

Let g ∈ F [X] be the minimal polynomial with the set of roots equal to D (evidently, deg g = |D|). Then the F -algebra of all functions f : D^{n} → F is isomorphic to the quotient algebra A = F [X_{1}, …, X_{n}]/(g(X_{1}), …, g(X_{n})).

The main purpose in the next sections is to obtain lower bounds on the complexity of depth 3 arithmetic circuits (1) for certain functions f ∈ A, thereby equality (1) is viewed in the algebra A.

Let us mention some easy properties of A which we use below (cf. [14], also [4]).

Lemma 1 a) A is an algebra of principal ideals;

b) for any f ∈ A the number of nonzeroes |{x ∈ D^{n} : f(x) ≠ 0}| coincides with the dimension of the principal ideal (f) ⊂ A.

Clearly, monomials of the form X_{1}^{i_{1}} ⋯ X_{n}^{i_{n}}, 0 ≤ i_{1}, …, i_{n} < |D|, constitute a basis of A, for an element f ∈ A we refer to its degree w.r.t. this basis. In abuse of notations we identify sometimes f with the corresponding polynomial in this basis.

Below it will be sometimes convenient to imagine a metric geometry in the space of monomials M = {X_{1}^{i_{1}} ⋯ X_{n}^{i_{n}}}_{0≤i_{1},...,i_{n}<|D|} endowed with the Hamming distance ρ (being equal to the number of distinct coordinates). If the minimal polynomial g ∈ F [X] of D is a binomial q = x^{ℓ} − a (obviously, g|(X^{q−1} − 1)) then M satisfies the following property.

Definition 1 We say that the algebra A has a multiplicative basis of the monomials M if

1) for any two monomials m_{1}, m_{2} ∈ M there is a monomial m ∈ M which equals to their product m = m_{1}m_{2} (in A);

2) the Hamming distance is invariant under multiplication: ρ(m_{1}, m_{2}) = ρ(m′m_{1}, m′m_{2}).

We note that the algebra of functions on F (see section 1), in other words D = F, g = X^{q} − X, satisfies the condition 1), whereas, fails to satisfy 2), it satisfies just the inequality ρ(m_{1}, m_{2}) ≥ ρ(m′m_{1}, m′m_{2}).

Definition 2 For any integer 2 ≤ d < q a linear d-sweep ℓs(d) (w.r.t. the field F = GF (q)) is the minimal ℓ (provided that it does exist) such that for any ℓ subsets D_{1}, …, D_{ℓ} ⊂ F, |D_{1}| = ⋯ = |D_{ℓ}| = d any linear function L(X_{1}, …, X_{ℓ}) = a_{1}X_{1} + ⋯ + a_{ℓ}X_{ℓ} + a with nonvanishing coefficients a_{1} ≠ 0, …, a_{ℓ} ≠ 0, sweeps L(D_{1} × ⋯ × D_{ℓ}) = F the entire F.

Lemma 2 a) ℓs(d) is defined if and only if d > p^{λ−1}, in this case ℓs(d) ≤ q − d + 1;

b) for d > q/2 we have ℓs(d) = 2.

3 Rigid rank and communication rank of a matrix.

In this section we consider matrices over arbitrary (not necessary finite) fields.

Let A = (a_{ij}) be k × n matrix and m ≥ 0 be an integer. For subsets I ⊂ {1, …, k}, J ⊂ {1, …, n} we denote by A_{I,J} the submatrix of A formed by its rows from I and the columns from J.

Definition 3 m-rigid rank rrk_{m}(A) of A is defined as the minimal possible rank of matrices which differ from A by at most of m entries in each row.

Definition 4 m-communication rank crk_{m}(A) of A is defined as the maximal possible number r of its rows I ⊂ {1, …, k}, |I| = r such that there exists a partition {1, …, n} = J_{0} ∪ ⋯ ∪ J_{m} of the set of its columns into (m + 1) subsets with the property that every submatrix A_{I,J_{ℓ}}, 0 ≤ ℓ ≤ m has the rank r.

Notice that both rrk_{m} and crk_{m} are not invariant in general with respect to transposing the matrix A. Obviously, rrk_{0} and crk_{0} coincide with the usual rank.

The next lemma relates the rigid and communication ranks.

Lemma 3 rrk_{m}(A) ≤ (m + 2) crk_{m}(A) ≤ (m + 2)(m + 1)rrk_{m}(A).

4 Upper bound on the number of nonzeroes of a product of linear functions via the communication rank.

Throughout this section we fix a product of linear functions Π = _{∏j}L_{j} (cf. (1)) and a subset D ⊂ F, denote d = |D|, viewing Π : D^{n} → F as a quasiboolean function (see section 2). Let L_{j} = ∑_{1≤i≤n}a_{j}^{(i)}X_{i} +a_{j} where a_{j}^{(i)}, a_{j} ∈ F.

By the ℓ_{1}-communication rank of Π we mean the ℓ_{1}-communication rank (see section 3) of the matrix A = (a_{j}^{(i)}) of its coefficients, L_{j} being treated as the rows of A (excluding the free coefficients of L_{j}). Denote ℓ = ℓs(d) (we assume that ℓ is defined, i.e. d > p^{λ−1}, then lemma 2a) entails that ℓ ≤ q − 1, see section 2).

The purpose of this section is to bound from above the number of nonzeroes of Π on D^{n} via the (ℓ − 1)-communication rank of Π.

Lemma 4 Let the (ℓ − 1)-communication rank of Π equal to r. Then the probability

P r[x ∈ D^{n} : Π(x) ≠ 0] ≤ exp(−Ω(r)).

5 Approximating depth 3 arithmetic circuits by sparse polynomials

In this section we show that if a quasi-boolean function f : D^{n} → F, |D| = d > p^{λ−1} can be computed by a depth 3 arithmetic circuit (1) with a small complexity N then f can be approximated by a polynomial of a special type (see theorem 2 below), in case D = F − {0} this polynomial is sparse (see lemma 5 below). For this purpose it suffices to approximate a product Π = ∏ L_{j} of linear functions.

Let ℓ = ℓs(d), recall that ℓ ≤ q − 1 due to lemma 2 (cf. also section 4). Again (cf. section 1) we fix a threshold r (which could be varied). The proof of the following theorem uses lemmas 3,4.

Theorem 2 For any r a product ∏_{j} L_{j} of linear functions can be approximated on D^{n} by a suitable function of the form

g_{1} = ∑_{1≤i≤exp(O(r))} ∏_{m} L_{i,m}  (3)

where L_{i,m} are linear functions such that for every i the number of m for which L_{i,m} has at least one zero in D^{n}, is bounded by O(r). The approximation means that the probability

P r [x ∈ D^{n} : ∏_{j} L_{j}(x) ≠ g_{1}(x)] ≤ exp(−Ω(r)).

If one would be able to prove that a particular function f : D^{n} → F for a certain r can not be approximated by a function of the form (3), then theorem 2 would imply a lower bound N ≥ exp(Ω(r)) on the complexity of computing f by a depth 3 arithmetic circuit (1).

We prove a complexity exponential lower bound in the next section for an explicitly given function f in case when |D| = q − 1, from now on we study this particular case.

Let {a} = F −D. Observe that the only linear functions L ∈ F [X_{1}, …, X_{n}] without zeroes in D^{n}, are {X_{i} − a}_{i} (up to constant factors), in particular, ℓ = ℓs(|D|) = 2 (cf. lemma 2b). For the sake of simplicity of notations we assume in the sequel that D = F^{∗} = F − {0}, nevertheless, all the further results still hold for any D = F − {a} by means of the linear transformation of the coordinates X_{i} → X_{i} + a, 1 ≤ i ≤ n.

Lemma 5 In case D = F^{∗} for any r a product Π = ∏_{j} L_{j} of linear functions can be approximated on D^{n} by an appropriate function of the form g̃ = ∏_{1≤i≤n} X_{i}^{μ_{i}} · g, 0 ≤ μ_{i} ≤ p − 2, 1 ≤ i ≤ n where deg g ≤ O(r). Again the approximation means that the probability

P r[x ∈ D^{n} : Π(x) ≠ g̃(x)] ≤ exp(−Ω(r))

As we mentioned already a similar statement is valid for any D = F −{a} by means of replacing g̃ for ∏_{1≤i≤n}(X_{i} − a)^{μ_{i}}g.

One can view g̃ from lemma 5 as a sparse (when r is relatively small) polynomial with less than n^{O(r)} monomials. Moreover, g̃ has a special structure and that is why we introduce the following definition.

Definition 5 A polynomial of the form ∑_{1≤η≤t} X^{I_{η}}g_{η} where X^{I_{η}} is a monomial and deg (g_{η}) ≤ r̃ is called (t, r̃)-sparse.

Lemma 5 implies the following proposition.

Proposition 1 There exists a constant δ_{0} > 0 such that if a function f : (F^{∗})^{n} → F can be computed by an arithmetic depth 3 circuit (1) with the complexity N ≤ exp(δ_{0}r) for a certain r then f can be approximated by a pertinent (N, O(r))-sparse function g, i.e.

P r[x ∈ (F^{∗})^{n} : f(x) ≠ g(x)] ≤ exp(−Ω(r))

6 Exponential lower bound for arithmetic depth 3 circuits computing the determinant or the permanent of matrices with nonzero entries

The main goal of this section is to prove an exponential lower bound on the complexity of an arithmetic depth 3 circuit (1) which computes either the determinant, either the permanent or the Hamiltonian cycles polynomial treated as a function : (F^{∗})^{n^{2}} → F. Also the lower bounds for some other explicitly given functions will be proved.

Although, we are interested mainly in the case D = F^{∗}, the next lemma is valid for any D ⊂ F, d = |D| such that the algebra of A of function D^{n} → F has a multiplicative basis of monomials M = {X_{1}^{i_{1}} ⋯ X_{n}^{i_{n}}}_{0≤i_{1},...,i_{n}<d} (see definition 1 in section 2). One can rephrase definition 5 using the (Hamming metric ρ) geometric language in M (cf. section 2): if a polynomial f is (t, r)- sparse then its support supp (f) ⊂ M (throughout this section the support is the set of monomials from M occurring in the polynomial) lies in a union of t balls each of a radius at most r (centered at X^{I_{η}}).

The following lemma provides a lower bound on the number of nonzeroes of a (t, r)-sparse polynomial.

Lemma 6 Let the algebra A of functions : D^{n} → F have a multiplicative basis M and for a certain R the support supp (f) of a (t, r)-sparse polynomial f ∈ A (where t ≥ n) contain a monomial X^{I^{(0)}} such that ρ(X^{I^{(0)}}, X^{I}) ≥ R for any other monomial X^{I^{(0)}} ≠ X^{I} ∈ supp (f). Then

P r[x ∈ D^{n} : f(x) ≠ 0] ≥ exp (−O (\frac{n}{R^{2}} (r + n^{4/3} log^{2/3} t)))  (4)

Remark 1 The imposed inequality t ≥ n is not essentially restrictive, because when t < n one could treat f as (n, r)-sparse polynomial. Thus, one can replace in (4) the occurrence of t by t + n getting rid of the restriction t ≥ n.

Proof of the lemma. Replacing f by f · (a X^{I^{(0)}})^{−1} where a ∈ F^{∗} is the coefficient at the monomial X^{I^{(0)}} in f (and taking into account that M is a multiplicative basis of A), we assume f is still (t, r)-sparse, 1 ∈ supp (f) and for any 1 ≠ X^{I} ∈ supp (f) we have ρ(1, X^{I}) ≥ R. We keep the notation X^{I_{η}} for the centers of the balls. One can deem that there are (t−1) balls centered at X^{I_{η}} and the monomial 1 lies in its own ball centered at 1. Taking any I_{η} and X^{I} ∈ supp (f) which lies in the ball of a radius at most r centered at X^{I_{η}}, we obtain that ρ(1, X^{I_{η}}) ≥ ρ(1, X^{∗}) − ρ(X^{∗}, X^{I_{η}}) ≥ R − r.

Put

s = \frac{Cn}{R}(r + n^{2/3} log^{1/3} t)  (5)

for an appropriate sufficiently large constant C which will be specified later. Consider the sphere S ⊂ M of the radius \frac{d−1}{d}n − s centered at 1 (w.l.o.g. we can assume that d|n), i.e. S = \{X^{J} : ρ(1, X^{J}) = \frac{d−1}{d}n − s\}. Since

|S| = (d − 1)^{\frac{d−1}{d} n−s} ( \begin{matrix}n \\ \frac{d−1}{d}n − s \end{matrix} ) ≥ d^{n} exp (−O (\frac{s^{2}}{n} \frac{d^{2}}{d − 1} + log n)) ,

we notice that the probability

P r[X^{J} ∈ M : X^{J} ∈ S] ≥ exp (−O (\frac{s^{2}}{n} )) ,

and the right side of the latter inequality has the same order of growth as the right side of the desired inequality (8).

W.l.o.g. we can assume that s < \frac{d−1}{d}n, because otherwise (4) is trivial. Let us view a polynomial from A as a row of its d^{n} coefficients at the

monomials from M. We suppose to prove that one can pick out at least half of the elements X^{J} from S such that the matrix composed of the rows X^{J}f for these X^{J} ∈ S contains the unit submatrix just in the set J of columns X^{J}. That means that the dimension of the ideal (f) ⊂ A is greater or equal to |S|/2. Then lemma 1b) (see section 2) would imply (4) due to the obtained above bound on |S|.

We call X^{J} ∈ S remote if ρ(X^{J}, X^{I_{η}}) > \frac{d−1}{d}n − s + r for all η. Observe that if we compose the above matrix of the rows X^{J}f for all remote X^{J} then it contains the desired unit submatrix. Indeed, any monomial 1 ≠ X^{I} ∈ supp (f) belongs to a ball centered at X^{I_{η}} for a certain η, with the radius r. Therefore,

ρ(X^{J}, X^{I}) ≥ ρ(X^{J}, X^{I_{η}}) − ρ(X^{I_{η}}, X^{I}) > \frac{d − 1}{d}n − s.

Hence for any X^{J_{0}} ∈ S (even not necessary to be remote) we have

ρ(X^{J}, X^{J_{0}}X^{I}) ≥ ρ(X^{J}, X^{I}) − ρ(X^{I}, X^{J_{0}}X^{I}) = ρ(X^{J}, X^{I}) − (\frac{d − 1}{d}n − s) ,

the latter equality invokes the property 2) from definition 1 (see section 2). Thus, ρ(X^{J}, X^{J_{0}}X^{I}) > 0 which means that the row X^{J_{0}}f can not have a nonzero entry in any column X^{J} for a remote X^{J} (see again definition 1), except for appearance of an entry equal to 1 in the column X^{J_{0}} (the latter appearance makes sense only if X^{J_{0}} ∈ J, i.e., X^{J_{0}} is remote).

In order to justify the remaining goal, i.e., to show that at least half of the elements X^{J} ∈ S are remote, it suffices to prove for every η that the probability

P r [X^{J} ∈ S : ρ(X^{J}, X^{I_{η}}) ≤ \frac{d − 1}{d}n − s + r] ≤ \frac{1}{2t}  (6)

Notice that one can assume that R ≥ 3r, otherwise (4) becomes trivial due to the occurrence of the first term \frac{nr^{2}}{R^{2}} .

Thus, we fix I_{η} and denote by U_{0}, …, U_{d−1} the partition of the set {1, …, n} where U_{j} consists of all i such that i-th coordinate of the vector I_{η} equals to j. Denote w_{j} = |U_{j}|, 0 ≤ j ≤ d−1. Introduce independent random variables Y_{1}, …, Y_{n} each taking the value 0 with the probability \frac{1}{d} + \frac{s}{n} and every value among 1, …, d − 1 with the probability \frac{1}{d} − \frac{s}{(d−1)n}.

Denote δ = \frac{1}{6} \frac{sR}{n^{2}} and w = \frac{1}{6d} \frac{sR}{n}. We say that U_{j} is large if w_{j} ≥ w. Fix a large U_{j} for the time being, denote by m_{j} the number of Y_{i} among i ∈ U_{j} such that Y_{i} = j. Then Chernoff’s inequality (see, e.g. [8]) states that

P r [|\frac{m_{j}}{w_{j}} − (\frac{1}{d} − \frac{s}{(d − 1)n})| ≥ δ] ≤ exp(−Ω(δ^{2}w_{j})) ≤ exp(−Ω(δ^{2}w))

(7)_{j}

in case when j ≥ 1 and

P r [|\frac{m_{0}}{w_{0}} − (\frac{1}{d} + \frac{s}{n})| ≥ δ] ≤ exp(−Ω(δ^{2}w_{0})) ≤ exp(−Ω(δ^{2}w)) (7)_{0}

in case when j = 0 where the probabilities are taken over the random variables Y_{1}, …, Y_{n}. We claim that one can achieve that

P r [n − (m_{0} + m_{1} + ⋯ + m_{d−1}) ≤ \frac{d − 1}{d}n − s + r] ≤ exp(−C_{0} log t) (8)

for an arbitrary constant C_{0} > 0 (by means of suitable specifying a constant C in (5)).

To estimate the sum n − (m_{0} + m_{1} + ⋯ + m_{d−1}) (being the Hamming distance between the monomials X_{1}^{Y_{1}} ⋯ X_{n}^{Y_{n}} and X^{I_{η}}), we handle separately the case of a large U_{j} applying the inequality m_{j} ≤ (\frac{1}{d} − \frac{s}{(d−1)n}) w_{j} + δw_{j}

when j ≥ 1 (see (7)_{j}) or the inequality m_{0} ≤ (\frac{1}{d} + \frac{s}{n}) w_{0} + δw_{0} when j = 0 (see (7)_{0}), and the case of a small U_{j} in which we simply apply the inequality m_{j} ≤ w_{j} ≤ w. Hence (with a probability greater than 1 − exp(−Ω(δ^{2}w))) the following inequality is true:

n − (m_{0} + m_{1} ⋯ + m_{d−1}) ≥ \frac{d − 1}{d}n − \frac{w_{0}s}{n} + \frac{(w_{1} + ⋯ + w_{d−1})s}{(d − 1)n} − δn − dw.

Since n − w_{0} = w_{1} + ⋯ + w_{d−1} = ρ(1, X^{I_{η}}) ≥ R − r ≥ \frac{2}{3}R (see the beginning of the proof of the lemma), we obtain

n − (m_{0} + m_{1} + ⋯ + m_{d−1}) ≥ \frac{d − 1}{d} n − s + \frac{2}{3} \frac{d}{d − 1} \frac{Rs}{n} − δn − dw.

Taking into account that \frac{2}{3} \frac{Rs}{n} ≥ 4δn, \frac{2}{3} \frac{Rs}{n} ≥ 4dw, \frac{2}{3} \frac{Rs}{n} ≥ 4r (the latter inequality can be secured by choosing a sufficiently large constant C in (5)) we deduce that the required in (8) inequality n − (m_{0} + m_{1} + ⋯ m_{d−1}) ≤ \frac{d−1}{d} n−s+r could be true with a probability less than exp(−Ω(δ^{2}w)). Again increasing a constant C in (5) if necessary, we can achieve that δ^{2}w ≥ C_{1} log t and thereby, prove (8).

Now to complete the proof of (6) we denote for brevity the event that among random values Y_{1}, …, Y_{n} there are exactly \frac{n}{d} + s zeroes, i.e. the monomial X_{1}^{Y_{1}} ⋯ X_{n}^{Y_{n}} belongs to the sphere S, by (Y_{1}, …, Y_{n}) ∈ S. Then

P r [n − (m_{0} + m_{1} + ⋯ + m_{d−1}) ≤ \frac{d − 1}{d} n − s + r] ≥

P r[(Y_{1}, …, Y_{n}) ∈ S]×

P r [n − (m_{0} + m_{1} + ⋯ + m_{d−1}) ≤ \frac{d − 1}{d}n − s + r|(Y_{1}, …, Y_{n}) ∈ S]

= P r [(Y_{1}, …, Y_{n}) ∈ S] P r [X^{J} ∈ S : ρ(X^{J}, X^{I_{η}}) ≤ \frac{d − 1}{d}n − s + r] ≥

\frac{1}{n + 1}P r [X^{J} ∈ S : ρ(X^{J}, X^{I_{η}}) ≤ \frac{d − 1}{d}n − s + r] ,  (9)

the latter inequality follows from the observation that the radius \frac{d−1}{d}n − s of the sphere S is the expectation of radii of (n + 1) possible spheres in which the monomial X_{1}^{Y_{1}} ⋯ X_{n}^{Y_{n}} could lie, and the probability for the monomial to lie in a sphere increases along with the radius of the sphere till \frac{d−1}{d}n − s and after that decreases.

Together with (8) for an appropriate constant C_{0} the inequality (9) implies (6), taking into account that t ≥ n, the lemma is proved.

From now on till the end of the paper we assume that D = F^{∗} (cf. the end of the previous section).

Denote by K = ℤ/(q − 1) the ring of residues. Recall that for a subset U ⊂ K^{n} of the free K-module its coding distance m = m(U) is defined as the minimum of ρ(u_{1}, u_{2}) over all pairs u_{1} ≠ u_{2}, u_{1}, u_{2} ∈ U. Denote by f_{U} = ∑_{u∈U} X^{u} : (F^{∗})^{n} → F the sum of the monomials with the exponents from U.

Theorem 3 There exists ϵ > 0 such that if the number of the elements n ≤ t = |U| ≤ exp(ϵ m^{6}/n^{5}) then for any depth 3 arithmetic circuit (1) computing f_{U} : (F^{∗})^{n} → F the complexity lower bound N ≥ t holds.

Proof. Suppose the contrary. Set r = ϵ_{1}m^{2}/n for a pertinent small enough ϵ_{1} > 0 which will be specified later. Applying to f_{U} proposition 1, provided that ϵ < δ_{0}ϵ_{1}, we obtain a (t−1, C_{1}r)-sparse polynomial g which approximates f_{U}:

P r[x ∈ (F^{∗})^{n} : f_{U}(x) ≠ g(x)] ≤ exp(−δ_{1}r)

for certain C_{1}, δ_{1} > 0.

Observe that (2t − 1, C_{2}r)-sparse polynomial f_{U} − g contains a monomial X^{I^{(0)}} ∈ M from the support supp (f_{U}) such that ρ(X^{I^{(0)}}, X^{I}) ≥ m/4 for any X^{I^{(0)}} ≠ X^{I} ∈ supp (f_{U} − g), provided that ϵ_{1} < \frac{1}{4C_{1}} . Indeed, denote by X^{I_{1}}, …, X^{I_{t−1}} the centers of the balls of radii at most C_{1}r which cover the support supp (g). Then at least for one of the monomials X^{I^{(0)}} ∈ supp (f_{U}) we have ρ(X^{I^{(0)}}, X^{I_{i}}) ≥ m/2 for 1 ≤ i ≤ t−1. Hence for any monomial X^{I} from the ball of the radius C_{1}r ≤ m/4 centered at X^{I_{i}} we have ρ(X^{I_{0}}, X^{I}) ≥ m/4.

Now we are able to apply lemma 6 to the polynomial f_{U} −g with R = m/4 which gives the bound

P r[x ∈ (F^{∗})^{n} : f_{U}(x) ≠ g(x)] ≥ exp (−C_{2}r (ϵ_{1} + \frac{ϵ^{2/3}}{ϵ_{1}} ))

for a suitable constant C_{2} appearing from the right side of (4). Now specifying

first ϵ_{1} < \frac{δ_{1}}{3C_{2}} and thereupon ϵ < (\frac{ϵ_{1}δ_{1}}{3C_{2}} )^{3/2} (and also satisfying ϵ < δ_{0}ϵ_{1}, see above), we get a contradiction which proves the theorem.

Take any prime p_{0}|(q−1) and consider a linear code U_{0} ⊂ (GF (p_{0}))^{n} with a basis u_{1}, …, u_{k} and the coding distance m. Then the subset U = \frac{(q−1)}{p_{0}}U_{0} ⊂ K^{n} obtained from U_{0} by multiplying every its element by \frac{q−1}{p_{0}} ∈ K, has also the coding distance m. Moreover, the following formula is valid:

f_{U} = ∏_{1≤i≤k} ( ∑_{0≤j≤p_{0}−1} X^{j \frac{q−1}{p_{0}} u_{i}}) : (F^{∗})^{n} → F  (10)

Using Gilbert-Varshamov bound from the coding theory [9], which supplies us with a linear code U of the coding distance m ≥ δ_{0}n for appropriate δ_{0} > 0 and the dimension k = ϵ_{0}n, where 0 < ϵ_{0} < ϵδ_{0}^{6} for the constant ϵ from theorem 3, we get the following corollary.

Corollary 2 There exists a linear code U_{0} ⊂ (GF (p_{0}))^{n} such that for any depth 3 arithmetic circuit (1) computing f_{U} : (F^{∗})^{n} → F the exponential lower bound on its complexity N ≥ exp(Ω(n)) holds.

If we would like to stick with explicitly constructed functions, we can consider a BCH code [9] with the coding distance m ≥ Ω(n/ log n), which has a linear dimension Ω(n), and as U_{0}^{(BCH)} we take an arbitrary its linear subcode (i.e. a subspace) of the dimension Ω(n/ log^{6} n). Again applying theorem 3, we get the following corollary.

Corollary 3 For an explicitly constructed function f_{U^{(BCH)}} : (F^{∗})^{n} → F (obtained from a BCH code) we have the exponential lower bound N ≥ exp(Ω(n/ log^{6} n)) on the complexity of any computing it depth 3 arithmetic circuit (1).

Finally, based on formula (10) which has a linear size O(n) and applying the construction from [15] (see also [2]) to the function f_{U} in the algebra A, we conclude with the following corollary.

Corollary 4 For each of the following three functions : (F^{∗})^{n^{2}} → F a) Determinant ∑_{π∈S_{n}}(−1)^{sgn(π)} ∏_{1≤i≤n} X_{i,π(i)};

b) Permanent ∑_{π∈S_{n}} ∏_{1≤i≤n} X_{i,π(i)};

c) Hamiltonian cycles polynomial ∑_{π} ∏_{1≤i≤n} X_{i,π(i)}, where the latter summation is taken over all permutations π which consist of a single cycle, any computing it depth 3 arithemtic circuit (1) has the exponential complexity N ≥ exp(Ω(n)).

References

[1] M.Agrawal, E.Allender, S.Datta, On T C^{0}, AC^{0}, and arithmetic circuits. ECCC Report TR97-016.

[2] J. von zur Gathen. Feasible arithmetic computations: Valiant’s hypothesis. J. Symp. Comput., 4, 1987, p. 137-172.

[3] D. Grigoriev. Lower bounds in algebraic complexity. J. Soviet Math., 29, 1985, p. 1388–1425.

[4] D. Grigoriev. Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. Theor. Comput. Sci., 180, 1997, p. 217–228.

[5] D. Grigoriev, M. Karpinski. An exponential lower bound for depth 3 arithmetic circuits. Proc. ACM Symp. Th. Comput., Dallas, 1998.

[6] J. Hastad, M. Goldmann. On the power of small-depth threshold circuits. Comput. Complexity, 1, 1991, p. 113–129.

[7] M. Krause, S. Waack. Variation ranks of communication marices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in. Proc. IEEE Symp. Found. Comput. Sci., 1991, p. 777– 782.

[8] E. Kushilevitz, N. Nisan. Communication complexity. Cambridge University Press, 1997.

[9] F. MacWilliams, N. Sloane. The theory of error-correcting codes. North-Holland, 1977.

[10] N. Nisan, A. Wigderson. Lower bound on arithmetic circuits via partial derivatives. Proc. IEEE Symp. Found. Comput. Sci., 1995, p. 16–25.

[11] A. Razborov. Lower bounds on the size of bounded depth ciruits over a complete basis with logical addition. Math. Notes, 41, 1987, p. 333–338.

[12] A. Razborov. On small depth threshold circuits. Lect. Notes Comput. Sci., 621, 1992, p. 42–52.

[13] A. Razborov, A. Wigderson. n^{Ω(log n)} lower bounds on the size of depth 3 threshold circuits with AND gates at the bottom. Inform. Proc. Lett., 45, 1993, p. 303–307.

[14] R. Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. Proc. ACM Symp. Th. Comput., 1987, p. 77–82.

[15] L. Valiant. Completeness classes in algebra. Proc. ACM Symp. Th. Comput. 1979, p. 259–261.

[16] A. Yao. On ACC and threshold circuits. Proc. IEEE Symp. Found. Comput. Sci., 1990, p. 619–627.