Chicago Journal of Theoretical Computer Science

MIT Press

Volume 1995, Article 2 21 July, 1995

ISSN 1073–0486. MIT Press Journals, 55 Hayward St., Cambridge, MA 02142; (617)253-2889; journals-orders@mit.edu, journals-info@mit.edu. Published one article at a time in L^{A}TEX source form on the Internet. Pagination varies from copy to copy. For more information and other articles see:

• http://www-mitpress.mit.edu/jrnls-catalog/chicago.html/

• http://www.cs.uchicago.edu/publications/cjtcs/

• gopher.mit.edu

• gopher.cs.uchicago.edu

• anonymous ftp at mitpress.mit.edu

• anonymous ftp at cs.uchicago.edu Grolmusz Weak mod m Representation of Boolean Functions (Info)

\begin{matrix}c \\ ◯ \end{matrix}1995 by Massachusetts Institute of Technology. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to insure fair attribution to authors and the journal, and to prohibit use in a competing commercial product. See the journal’s World Wide Web site for further details. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; journals-rights@mit.edu.

The Chicago Journal of Theoretical Computer Science is a peer-reviewed scholarly journal in theoretical computer science. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in Computer Science.

Editor in chief: Janos Simon

Consulting editors: Joseph Halpern, Stuart A. Kurtz, Raimund Seidel

Editors:

Martin Abadi  Greg Frederickson John Mitchell
Pankaj Agarwal Andrew Goldberg Ketan Mulmuley
Eric Allender Georg Gottlob Gil Neiger
Tetsuo Asano  Vassos Hadzilacos David Peleg
Laszló Babai  Juris Hartmanis Andrew Pitts
Eric Bach  Maurice Herlihy James Royer
Stephen Brookes Stephen Homer  Alan Selman
Jin-Yi Cai Neil Immerman Nir Shavit
Anne Condon  Paris Kanellakis Eva Tardos
Cynthia Dwork Howard Karloff  Sam Toueg
David Eppstein Philip Klein  Moshe Vardi
Ronald Fagin  Phokion Kolaitis Jennifer Welch
Lance Fortnow Stephen Mahaney Pierre Wolper
Steven Fortune Michael Merritt

Managing editor: Michael J. O’Donnell

Electronic mail: chicago-journal@cs.uchicago.edu

[ii]

On the Weak mod m Representation of Boolean Functions

Vince Grolmusz

21 July, 1995

Abstract

Let P be a polynomial over the ring of mod m integers. P weakly

Abstract-1

represents Boolean function f: {0, 1}^{n} → {0, 1} if there is a subset S ⊆ {0, 1, …, m − 1} such that f(x) = 0 if and only if P (x) ∈ S. The smallest degree of polynomials P weakly representing f is called the weak mod m degree of f. We give here an Ω(log n) lower bound for the weak degree of the generalized inner product function (GIP) of Babai, Nisan, and Szegedy [BNS92]. This is the first lower-bound result for the weak degree of a Boolean function that does not deteriorate if the number of prime divisors of m increases.

In the second part of the paper, we give superpolynomial lower

Abstract-2

bounds for the number of monomials with nonzero coefficients in polynomials weakly representing the OR and the GIP∘PARITY functions.

1 Introduction

One of the central problems of theoretical computer science is the estimation

1-1

of the computational complexity of Boolean functions. One well studied measure of the complexity of Boolean function f is the degree of a polynomial P, which best approximates or represents f in some sense (see [Raz87], [Smo87], [NS94], [ABFR91], or [Bei93] for a survey). According to this approach, a Boolean function is considered “hard” if the polynomial that represents or best approximates it has a high degree.

Barrington, Beigel, and Rudich [BBR94] defined the mod m degree of

1-2

Boolean function f to be the smallest degree of any polynomial P over the

Grolmusz Weak mod m Representation of Boolean Functions §1

1 ring of mod m integers such that, for all 0–1 assignments of x, f(x) = 0 if and only if P (x) = 0. They obtained the following surprising result: The mod m degree of the n-variable OR function is O(n^{1/r}), where r is the number of distinct prime factors of m.

Since some computationally very similar functions, including OR and

1-3

AND, as well as mod m and ¬ mod m, have different mod m degrees, the weak mod m degree, a more robust measure, is defined in [BBR94]:

Definition 1 Let f: {0, 1}^{n} → {0, 1} be a Boolean function, and let P be defined as a polynomial of n variables over ℤ_{m} (the integers mod m),

P (x_{1}, x_{2}, …, x_{n}) = ∑_{H∈H} a_{H} ∏_{i∈H} x_{i}

where H ⊆ 2^{{1,2,... ,n}} and 0 ≠ a_{H} ∈ ℤ_{m}. We say that P weakly represents f if there is a set S ⊆ {0, 1, …, m − 1} such that, for every x ∈ {0, 1}^{n},

f(x) = 0 ⟺ P (x) ∈ S

Let Δ(f, m) be the minimum degree of polynomials mod m that weakly represent f. The size of polynomial P is defined to be |H|. Let Σ(f, m) denote the minimum size of polynomials mod m that weakly represent f.

Note that the mod m degree and the weak mod m degree of the OR function are the same.

Tardos and Barrington [TB95] proved an Ω(log n) lower bound for the

1-4

weak mod m degree of the OR function, if m has only two distinct prime divisors. More generally, if the number of distinct prime divisors of m is r, and the smallest prime divisor is q, then their lower bound is

Δ(OR, m) ≥ (1/(q − 1) − o(1))(log n)^{1/(r−1)}  (1)

The following function was first defined by Babai, Nisan, and Szegedy

1-5

[BNS92]:

Definition 2 Let A ∈ {0, 1}^{l×k}. Let GIP_{l,k}(A) denote the number of all-1 rows in matrix A, mod 2.

This is the mod 2 generalized inner product of the columns of A. 1-6 Here we show an Ω(log n) lower bound for Δ(GIP_{l,k}, m), where m is an

arbitrary integer (i.e., our lower bound does not deteriorate when the number of different prime divisors of m increases):

2 Theorem 1 Let l and k be positive integers that satisfy c log l < k ≤ (1/3) log l for some 0 < c < 1/3, and let n = kl. Then for every integer m that satisfies 1 < m ≤ exp(n^{1/4}),

Δ(GIP_{l,k}, m) ≥ k = Ω(log n)

This is the tightest possible lower bound that holds for m = 2, since the definition of GIP_{l,k} is just a polynomial mod 2 of degree k: the sum mod 2 of the product of each row.

Unfortunately, our degree lower bound method does not apply to the

1-7

theoretically interesting case when f is the OR function. However, we can prove that the size of the polynomials weakly representing OR must be large:

Theorem 2

1. Let m be the product of two different primes. Then there exists a constant c_{m} > 0 such that

Σ(OR, m) ≥ n^{c_{m} log n}

2. Suppose that m has r different prime divisors. Then there exists a constant c_{m} > 0 such that

Σ(OR, m) ≥ n^{c_{m}(log n)^{1/(r−1)}}

The proof of Theorem 2 is based on the method of Razborov and Wigder-

1-8

son [RW93] and the degree lower bound (1) of Tardos and Barrington [TB95]. Consequently, the bound depends on the number of prime divisors of m. Using the degree lower bound of our Theorem 1, we give a lower bound for the size, which does not deteriorate if the number of prime divisors of m increases.

Razborov and Wigderson [RW93] used the function

1-9

f_{n}(x) = ⨁_{i=1}^{h} ⋀_{j=1}^{⌊\frac{1}{3} log h⌋} ⨁_{k=1}^{h} x_{ijk}

to prove an Ω(n^{log n}) lower bound on size for some depth-3 circuits, where n = h^{2}⌊(1/3) log h⌋. Observe that f_{n} is the composition of the GIP and the PARITY functions.

Theorem 3 Let m > 1 be an arbitrary integer. Then

Σ(f_{n}, m) = n^{Ω(log n)}

3

2 Communication Complexity

Our main tool in proving Theorem 1 is a multiparty communication game.

2-1

In a multiparty communication game [CFL83], k players, p_{1}, p_{2}, …, p_{k}, intend to compute the value of g(A_{1}, A_{2}, …, A_{k}) cooperatively, where g: {0, 1}^{l×k} → {0, 1} and A_{i} ∈ {0, 1}^{l}, for i = 1, 2, …, k. Player p_{i} knows the value of each variable, except A_{i}. The players have unlimited computational power, and they communicate with the help of a blackboard viewed by all players. Only one player may write on the blackboard at a time. The goal is to compute g(A_{1}, A_{2}, …, A_{k}) in such a way that at the end of the computation, all players know this value. The cost of the computation is the number of bits written on the blackboard for the given A = (A_{1}, A_{1}, …, A_{k}) ∈ {0, 1}^{l×k}.

The cost of a multiparty protocol is the maximum number of bits com-

2-2

municated for any A in {0, 1}^{l×k}. The k-party communication complexity of a function g, C^{(k)}(g), is the minimum of the costs of those k-party protocols that compute g. Babai, Nisan, and Szegedy examined the multiparty communication complexity of the GIP function in [BNS92], and they proved the following theorem.

Theorem 4 ([BNS92], Theorem 2)

C^{(k)}(GIP_{l,k}) = Ω(l/4^{k})

3 Proving the Degree Bound

The proof is based on Theorem 4 and on an idea from [GH90].

3-1

Proof of Theorem 1 From Theorem 4, with k < (1/2 − ν) log n players,

Proof of Theorem 1-1

for some ν > 0,

C^{(k)}(GIP_{l,k}) ≥ cl/4^{k} = n^{Ω(1)}

On the other hand, suppose that some mod m polynomial P of degree k − 1 weakly represents GIP_{l,k}. Then the following k-player protocol can evaluate P with a small number of communicated bits. P is the sum of several monomials of degree at most k − 1. Since for each variable of a monomial there is at most one player who does not know it, for every monomial there exists a player who knows all of its variables. Before starting the communication game for P, the players agree on who computes each monomial. Then each player—without any communication—privately computes the mod m sum of

4 their assigned monomials. Next, communicating k⌈log(m + 1)⌉ bits, each player announces this mod m sum, and every player privately adds up the numbers seen. Now, if the result is in the set S, then GIP_{l,k} = 0; otherwise, it is 1.

From the preceding paragraph and Theorem 4,

Proof of Theorem 1-2

k⌈log(m + 1)⌉ ≥ C^{(k)}(GIP_{l,k}) = n^{Ω(1)}

which leads to a contradiction.

Proof of Theorem 1 □

4 Random Restrictions and the Size Bounds

Proof of Theorem 2 To prove part 1, let

Proof of Theorem 2-1

P (x_{1}, x_{2}, …, x_{n}) = ∑_{H∈H} a_{H} ∏_{i∈H} x_{i}

be a mod m polynomial, weakly representing the OR of n variables, where H ⊆ 2^{{1,2,... ,n}} and 0 ≠ a_{H} ∈ ℤ_{m}. We apply random restrictions independently to each variable x_{i}, for i = 1, 2, …, n, in a similar fashion to Ajtai [Ajt83], Furst, Saxe, and Sipser [FSS84] and Razborov and Wigderson [RW93]. Let

ρ(x_{i}) = \{ \begin{matrix}0 & with probability 1 − p \\ ∗ & with probability p \end{matrix}

where ρ(x_{i}) = ∗ means that x_{i} remains unrestricted, and p = (1/2)n^{−1/2}. For every c > 0 and |H| ≥ (c/2) log n,

Proof of Theorem 2-2

Pr ( ∏_{i∈H} ρ(x_{i}) ≠ 0) ≤ p^{\frac{c}{2} log n} ≤ n^{− \frac{c}{4} log n}  (2)

Suppose that |H|, the size of P, satisfies |H| ≤ n^{ε log n}, for a small enough ε > 0. Then, because of (2), the degree of the polynomial after the restriction will be small with high probability:

Pr(deg(P ∘ ρ) < (c/2) log n) = 1 − o(1)

Grolmusz Weak mod m Representation of Boolean Functions (Ref)

5 while P ∘ ρ still represents the OR of at least \sqrt{n} variables with probability 1 − o(1). So, from (1), setting c = (1/(q − 1) − o(1)), where q is the smallest prime divisor of m, we arrive at a contradiction.

Part 2 can be proved in similar fashion, using inequality (1) with r ≥ 2

Proof of Theorem 2-3

instead of r = 2. The details are left to the reader.

Proof of Theorem 2 □

Proof of Theorem 3 Let

P (x_{1}, x_{2}, …, x_{n}) = ∑_{H∈H} a_{H} ∏_{i∈H} x_{i}

be a mod m polynomial, weakly representing f_{n}. We apply random restrictions independently to each variable x_{i}, for i = 1, 2, …, n, as in the proof of Theorem 2, or as in [Ajt83], [FSS84], or [RW93]. Let

ρ(x_{i}) = \{ \begin{matrix}0 & with probability (1 − p)/2 \\ 1 & with probability (1 − p)/2 \\ ∗ & with probability p \end{matrix}

where p = (2 ln h)/h. Then, as in the proof of Theorem 2, or as in the proof of Theorem 3 in [RW93], if

|H| ≤ n^{ε log n}

for a sufficiently small ε > 0, then

Pr(deg(P ∘ ρ) < ⌊(1/3) log h⌋) ≥ 1 − o(1)  (3)

while

Pr (⨁_{k=1}^{h} ρ(x_{ijk}) is a constant) = (1 − p)^{h} ≤ 1/h^{2}

So, from (3) we conclude that—after fixing some more variables—there exists a mod m polynomial that weakly represents GIP_{l,k} with degree less than ⌊(1/3) log h⌋, and this contradicts our Theorem 1.

Proof of Theorem 3 □

5 Acknowledgments

The author is indebted to David Barrington and to Gábor Tardos for discus-

5-1

sions on this subject, and to Alexander Razborov, who directed the author’s attention to the random restriction techniques.

6 Acknowledgement of support: The author acknowledges the support of the grants OTKA 4271, OTKA F 014919, and of the Magyar Tudományért Foundation.

References for CJTCS Volume 1995, Article 2

References

[ABFR91] James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich. The expressive power of voting polynomials. In Proceedings of the 23rd ACM Symposium on Theory of Computation, pages 402–409. Association for Computing Machinery, 1991.

[Ajt83] Miklós Ajtai. ∑_{1}^{1} formulae on finite structures. Annals of Pure and Applied Logic, 24:1–48, 1983.

[BBR94] David A. Mix Barrington, Richard Beigel, and Steven Rudich. Representing Boolean functions as polynomials modulo composite numbers. Computational Complexity, 4:367–382, 1994. Also appeared in Proceedings of the 24th ACM Symposium on Theory of Computing, 1992.

[Bei93] Richard Beigel. The polynomial method in circuit complexity. In Proceedings of the 8th Annual Conference on Structure in Complexity Theory, pages 82–95. Institute of Electrical and Electronics Engineers, IEEE Computer Society Press, 1993.

[BNS92] László Babai, Noam Nisan, and Márió Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space tradeoffs. Journal of Computer and System Sciences, 45:204–232, 1992.

[CFL83] Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party protocols. In Proceedings 15th ACM Symposium on Theory of Computing, pages 94–99. Association for Computing Machinery, 1983.

7 [FSS84] Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity,

circuits and the polynomial time hierarchy. Mathematical Systems Theory, 17:13–27, 1984.

[GH90] Mikael Goldmann and Johann Håstad. On the power of the smalldepth threshold circuits. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 610–618. Institute of Electrical and Electronics Engineers, 1990.

[NS94] Noam Nisan and Márió Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:462–467, 1994. Also apeared in Proceedings of the 24th ACM Symposium on Theory of Computing, 1992.

[Raz87] Alexander Razborov. Lower bounds for the size of circuits of bounded depth with basis (AND, XOR). Mathematical Notes of the Academy of Science of the USSR, 41(4):333–338, 1987.

[RW93] Alexander Razborov and Avi Wigderson. n^{Ω(log n)} lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Information Processing Letters, 45(6):303–307, April 1993.

[Smo87] Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on Theory of Computing, pages 77–82. Association for Computing Machinery, 1987.

[TB95] Gábor Tardos and David A. Mix Barrington. A lower bound on the MOD 6 degree of the OR function. In Proceedings of the 3rd Israel Symosium on the Theory of Computing and Systems, pages 52–56, 1995.

8