% The Chicago Journal of Theoretical Computer Science, Volume 1995, Article 2
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1995 by Massachusetts Institute of Technology
%
\newtoks\rstyle
\rstyle={cjlook}
%
\ifx\documentclass\undeftex
\documentstyle[v1.1,published]{cjstruct}
\else
\documentclass[v1.1,published]{cjstruct}
\fi
%
% Local resources for this article.
%
\usestyleresource{amstex}
%
% Local macro definitions for this article.
%
\ifltwoe\else\newcommand{\emph}[1]{{\em #1\/}}\fi
\ifltwoe\else\newcommand{\textit}[1]{{\it #1\/}}\fi
\ifltwoe\else\newcommand{\textbf}[1]{{\bf #1\/}}\fi
\ifltwoe\else\newcommand{\textup}[1]{{\rm #1\/}}\fi
\ifltwoe\else\newcommand{\mathbf}[1]{{\bf #1\/}}\fi
\ifltwoe\else\newcommand{\mathcal}[1]{{\cal #1\/}}\fi
\ifltwoe\else\newcommand{\upshape}{\fontshape{n}\selectfont}\fi
%
\newcommand{\prooffontshape}{\upshape}
%
\mathstyleclass{\function}{\mathord}{\textup}
\newcommand{\universe}[1]{\Bbb{#1}}
\newcommand{\polynomial}[1]{#1}
\newcommand{\player}[1]{\mathbf{#1}}
\newcommand{\setofset}[1]{\mathcal{#1}}
\newcommand{\umod}{\mathop{\bmod}}
\newcommand{\orderge}[1]{\Omega(#1)}
\newcommand{\orderlt}[1]{o(#1)}
\newcommand{\orderle}[1]{O(#1)}
\newcommand{\logicnot}{\neg}
\newcommand{\logicequiv}{\Longleftrightarrow}
\newcommand{\logiciterand}{\bigwedge}
\newcommand{\logiciterxor}{\bigoplus}
\newcommand{\condval}[1]{\left\{\begin{array}{ll}#1\end{array}\right.}
\newcommand{\funcspace}[2]{#1\mathbin{\rightarrow}#2}
\newcommand{\oftype}{\colon}
\newcommand{\funccomp}{\circ}
\newcommand{\setsize}[1]{\left|#1\right|}
%
% end of local macro definitions for this article
%
\begin{document}
%
\begin{articleinfo}
%
\publisher{MIT Press}
%
\publishercomment{%
  {\Large
    \begin{center}
      Volume 1995, Article 2\\
      \textit{21 July, 1995}
    \end{center}
  }
  \par\noindent
  ISSN 1073--0486\@. MIT Press Journals, 55 Hayward St., Cambridge, MA
  02142; (617)253-2889;
  \emph{journals-orders@mit.edu, journals-info@mit.edu}\@.
  Published one article at a time in \LaTeX\ source form on the
  Internet\@. Pagination varies from copy to copy\@. For more
  information and other articles see:
  \begin{itemize}
    \item \emph{http://www-mitpress.mit.edu/jrnls-catalog/chicago.html/}
    \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/}
    \item \emph{gopher.mit.edu}
    \item \emph{gopher.cs.uchicago.edu}
    \item anonymous \emph{ftp} at \emph{mitpress.mit.edu}
    \item anonymous \emph{ftp} at \emph{cs.uchicago.edu}
  \end{itemize}
\sentence
}
%
\copyrightstmt{%
  \copyright 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;
  \emph{journals-rights@mit.edu}\@.\pagebreak[2]
}
%
\journal{Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science}
%
\journalcomment{%
  The \emph{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\@.
  \par
  \begin{trivlist}
    \item[\emph{Editor in chief:}] Janos Simon
    \item[\emph{Consulting editors:}]
      Joseph Halpern, Stuart A.\ Kurtz, Raimund Seidel
    \item[\emph{Editors:}]
      \begin{tabular}[t]{lll}
        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\'o 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
      \end{tabular}
    \item[\emph{Managing editor:}] Michael J.\ O'Donnell
    \item[\emph{Electronic mail:}] \emph{chicago-journal@cs.uchicago.edu}
  \end{trivlist}
\sentence
}
%
\bannerfile{cjtcs-banner.tex}
%
\volume{1995}
%
\articleid{2}
%
\selfcitation{
     @article{cj95-02,
       author={Vince Grolmusz},
       title={On the Weak \(\mathop{\bmod}m\) Representation of
              {B}oolean Functions},
       journal={Chicago Journal of Theoretical Computer Science},
       volume={1995},
       number={2},
       publisher={MIT Press},
       month={July},
       year={1995}
     }
}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\title{On the Weak \(\umod m\) Representation of Boolean Functions}
\shorttitle{Weak \(\umod m\) Representation of Boolean Functions}
\collectiontitle{}
\begin{authorinfo}
%
% Correction to error in cjstruct.sty version 1.1.
%
\def\fixversion{1.1}
\ifx\cjversion\fixversion
  \renewcommand{\printname}[1]{
    \global\authorstring={#1}
    \global\authorstrue
    \ifinfo\item Printed name: #1\fi
  }
\fi
%
% End of correction.
%
   \printname{Vince Grolmusz}
   \collname{}{Grolmusz, Vince}
   \begin{institutioninfo}
       \instname{E\"otv\"os University}
       \department{Department of Computer Science}
       \address{M\'uzeum krt.\ 6-8}{Budapest}{}{Hungary}{H-1088}
   \end{institutioninfo}
   \email{grolmusz@cs.elte.hu}
\end{authorinfo}
%
\shortauthors{Grolmusz}
%
\support{The author acknowledges the support of the grants OTKA 4271,
OTKA F~014919, and of the Magyar Tudom\'any\'ert Foundation\@.}
%
\begin{editinfo}
  \submitted{25}{1}{1995}\reported{5}{5}{1995}
  \submitted{6}{4}{1995}
  \submitted{24}{5}{1995}\reported{25}{5}{1995}\published{21}{7}{1995}
\end{editinfo}
\end{articleinfo}
%
\begin{articletext}
\begin{abstract}  
%
\begin{sloppypar}
\apar{Abstract-1}
Let \(\polynomial{P}\) be a polynomial over the ring of \(\umod m\) integers\@.
\(\polynomial{P}\) \emph{weakly represents} Boolean function
\(f\oftype\funcspace{\{0,1\}^n}{\{0,1\}}\) if there is a subset
\(S\subseteq{\{0,1,\ldots,m-1\}}\) such that \(f(x)=0\) if and only if
\(\polynomial{P}(x)\in S\)\@. The smallest degree of polynomials
\(\polynomial{P}\) weakly representing \(f\) is called the \emph{weak
\(\umod m\) degree of \(f\)}\@. We give here an \(\orderge{\log n}\)
lower bound  for the weak degree of the generalized inner product
function (\(\function{GIP}\)) of Babai, Nisan, and Szegedy
\cite{cj95-02-5}\@. 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\@.
%
\apar{Abstract-2}
In the second part of the paper, we give superpolynomial lower bounds
for the number of monomials with nonzero coefficients in polynomials
weakly representing the \(\function{OR}\) and the
\(\function{GIP}\funccomp\function{PARITY}\) functions\@.
\end{sloppypar}
% 
\end{abstract} 
% 
\asection{1}{Introduction} 
%
\apar{1-1}
One of the central problems of theoretical computer science is
the estimation of the computational complexity of Boolean
functions\@. One well studied measure of the complexity of Boolean
function \(f\) is the \emph{degree} of a polynomial
\(\polynomial{P}\), which best \emph{approximates} or
\emph{represents} \(f\) in some sense (see \cite{cj95-02-10},
\cite{cj95-02-12}, \cite{cj95-02-9}, \cite{cj95-02-1}, or
\cite{cj95-02-4} 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\@.
%
\apar{1-2}
Barrington, Beigel, and Rudich \cite{cj95-02-3} defined the \(\umod m\)
degree of Boolean function \(f\) to be the smallest degree of any
polynomial \(\polynomial{P}\) over the ring of \(\umod m\) integers
such that, for all \(0\)--\(1\) assignments of \(x\), \(f(x)=0\) if
and only if \(\polynomial{P}(x)=0\)\@. They obtained the following
surprising result: The \(\umod m\) degree of the \(n\)-variable
\(\function{OR}\) function is \(\orderle{n^{1/r}},\) where \(r\) is
the number of distinct prime factors of \(m\)\@.
%
\apar{1-3}
Since some computationally very similar functions, including
\(\function{OR}\) and \(\function{AND}\), as well as \(\umod m\) and
\(\logicnot\umod m\), have different \(\umod m\) degrees, the
\emph{weak \(\umod m\) degree}, a more robust measure, is defined in
\cite{cj95-02-3}:
%
\begin{alabsubtext}{Definition}{1}{}
Let \(f\oftype\funcspace{\{0,1\}^n}{\{0,1\}}\) be a Boolean function,
and let \(\polynomial{P}\) be defined as a polynomial of \(n\)
variables over \(\universe{Z}_m\) (the integers \(\umod m\)),
%
\[
\polynomial{P}(x_1,x_2,\ldots,x_n)=
  \sum_{H\in\setofset{H}}a_H\prod_{i\in H}x_i
\]
%
where \(\setofset{H}\subseteq2^{\{1,2,\ldots,n\}}\) and
\(0\ne a_H\in\universe{Z}_m\)\@. We say that \(\polynomial{P}\)
\emph{weakly represents} \(f\) if there is a set
\(S\subseteq\{0,1,\ldots,m-1\}\) such that, for every
\(x\in\{0,1\}^n\),
%
\[f(x)=0\logicequiv\polynomial{P}(x)\in S\]
%
\sentence
Let \(\Delta(f,m)\) be the minimum degree of polynomials \(\umod m\)
that weakly represent \(f\)\@. The \emph{size} of polynomial
\(\polynomial{P}\) is defined to be \(\setsize{\setofset{H}}\)\@. Let
\(\Sigma(f,m)\) denote the minimum size of polynomials \(\umod m\)
that weakly represent \(f\)\@.
\end{alabsubtext}
%
Note that the \(\umod m\) degree and the weak \(\umod m\) degree of
the \(\function{OR}\) function are the same\@. 
%
\apar{1-4}
Tardos and Barrington \cite{cj95-02-13} proved an \(\orderge{\log n}\) lower
bound for the weak \(\umod m\) degree of the \(\function{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
%
\begin{aequation}{1}
  \Delta(\function{OR},m)\geq\bigl(1/(q-1)-\orderlt{1}\bigr)
  (\log n)^{1/(r-1)}
\end{aequation}
\sentence
%
\apar{1-5}
The following function was first defined by Babai, Nisan, and Szegedy
\cite{cj95-02-5}:
%
\begin{alabsubtext}{Definition}{2}{}
Let \(A\in \{0,1\}^{l\times k}\)\@. Let
\(\function{GIP}_{l,k}(A)\) denote the number of all-\(1\) rows in
matrix \(A\), \(\umod 2\)\@.
\end{alabsubtext}
This is the \(\umod 2\) generalized inner product of the columns of
\(A\)\@.
%
\apar{1-6}
Here we show an \(\orderge{\log n}\) lower bound for
\(\Delta(\function{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):
%
\begin{alabsubtext}{Theorem}{1}{}
Let \(l\) and \(k\) be positive integers that satisfy
\(c\log l<k\leq(1/3)\log l\) for some \(0<c<1/3\), and
let \(n=kl\)\@. Then for every integer \(m\) that satisfies
\(1<m\leq\exp(n^{1/4})\),
%
\[\Delta(\function{GIP}_{l,k},m)\geq k=\orderge{\log n}\]
%
\sentence
\end{alabsubtext}
%
This is the tightest possible lower bound that holds for \(m=2\),
since the definition of \(\function{GIP}_{l,k}\) is just a
polynomial \(\umod 2\) of degree \(k\): the sum \(\umod 2\) of the
product of each row\@.
%
\apar{1-7}
Unfortunately, our degree lower bound method does not apply to the
theoretically interesting case when \(f\) is the \(\function{OR}\)
function\@. However, we can prove that the \emph{size} of the
polynomials weakly representing \(\function{OR}\) must be large:
%
\begin{alabsubtext}{Theorem}{2}{}
\ \par
\begin{enumerate}
%
\item[1.] Let \(m\) be the product of two different primes\@. Then there
exists a constant \(c_m>0\) such that
%
\[\Sigma(\function{OR},m)\geq n^{c_m\log n}\]
%
\sentence
%
\item[2.] Suppose that \(m\) has \(r\) different prime divisors\@. Then
there exists a constant \(c_m>0\) such that
%
\[\Sigma(\function{OR},m)\geq n^{c_m(\log n)^{1/(r-1)}}\]
%
\sentence
%
\end{enumerate}
\end{alabsubtext}
%
\apar{1-8}
The proof of Theorem~2 is based on the method of Razborov and
Wigderson \cite{cj95-02-11} and the degree lower bound (1) of Tardos and
Barrington \cite{cj95-02-13}\@. 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\@.
%
\apar{1-9}
Razborov and Wigderson \cite{cj95-02-11} used the function 
\[
  f_n(x)=\logiciterxor_{i=1}^{h}
  \logiciterand_{j=1}^{\left\lfloor\frac{1}{3}\log h\right\rfloor}
  \logiciterxor_{k=1}^{h}x_{ijk}
\]
to prove an \(\orderge{n^{\log n}}\) lower bound on size for some
depth-3 circuits, where \(n=h^2\lfloor(1/3)\log h\rfloor\)\@. Observe
that \(f_n\) is the composition of the \(\function{GIP}\) and the
\(\function{PARITY}\) functions\@.
%
\begin{alabsubtext}{Theorem}{3}{}
Let \(m>1\) be an arbitrary integer\@. Then 
%
\[\Sigma(f_n,m)=n^{\orderge{\log n}}\]
%
\sentence
\end{alabsubtext}
%
\asection{2}{Communication Complexity} 
%
\begin{sloppypar}
\apar{2-1}
Our main tool in proving Theorem~1 is a \emph{multiparty communication
game}\@. In a multiparty communication game \cite{cj95-02-6}, \(k\)
players, \(\player{p}_1,\player{p}_2,\ldots,\player{p}_{k}\), intend
to compute the value of \(g(A_1,A_2,\ldots,A_{k})\) cooperatively,
where \({g\oftype\funcspace{\{0,1\}^{l\times k}}{\{0,1\}}}\) and
\(A_i\in\{0,1\}^l\), for \(i=1,2,\ldots,k\)\@. Player \(\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,\ldots,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,\ldots,A_k)\in\{0,1\}^{l\times k}\)\@.
\end{sloppypar}
%
\apar{2-2}
The cost of a multiparty protocol is the maximum number of bits
communicated for any \(A\) in \(\{0,1\}^{l\times 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 \(\function{GIP}\) function in
\cite{cj95-02-5}, and they proved the following theorem\@.
%
\begin{alabsubtext}{Theorem}{4}{\protect\cite{cj95-02-5}, Theorem 2}
%
\[C^{(k)}(\function{GIP}_{l,k})=\orderge{l/{4^k}}\]
%
\sentence
\end{alabsubtext}
%
\asection{3}{Proving the Degree Bound} 
%
\apar{3-1}
The proof is based on Theorem~4 and on an idea from \cite{cj95-02-8}\@.
%
\begin{alabsubtext}{Proof of Theorem}{1}{}
\prooffontshape
%
\apar{Proof of Theorem 1-1}
From Theorem~4, with \(k<(1/2-\nu)\log n\) players, for some \(\nu>0\), 
\[
  C^{(k)}(\function{GIP}_{l,k})\geq cl/4^k=n^{\orderge{1}}
\]
\sentence
On the other hand, suppose that some \(\umod m\) polynomial
\(\polynomial{P}\) of degree \(k-1\) weakly represents
\(\function{GIP}_{l,k}\)\@. Then the following \(k\)-player protocol
can evaluate \(\polynomial{P}\) with a small number of communicated
bits\@. \(\polynomial{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 \(\polynomial{P}\), the players agree on who
computes each monomial\@. Then each player---without any
communication---privately computes the \(\umod m\) sum of their
assigned monomials\@. Next, communicating \(k\lceil\log(m+1)\rceil \)
bits, each player announces this \(\umod m\) sum, and every player
privately adds up the numbers seen\@. Now, if the result is in the set
\(S\), then \(\function{GIP}_{l,k}=0\); otherwise, it is 1\@.
%
\apar{Proof of Theorem 1-2}
{\samepage
From the preceding paragraph and Theorem~4,
\[
  k\lceil\log(m+1)\rceil\geq C^{(k)}(\function{GIP}_{l,k})=n^{\orderge{1}}
\]
which leads to a contradiction\@. 
%
{\samepage\markendlst{Proof of Theorem 1}}
}
\end{alabsubtext}
%
\asection {4}{Random Restrictions and the Size Bounds}
%
\begin{alabsubtext}{Proof of Theorem}{2}{}
\prooffontshape
%
\apar{Proof of Theorem 2-1}
To prove part 1, let 
\[
\polynomial{P}(x_1,x_2,\ldots,x_n)=\sum_{H\in\setofset{H}}a_H\prod_{i\in H}x_i
\]
be a \(\umod m\) polynomial, weakly representing the
\(\function{OR}\) of \(n\) variables, where
\(\setofset{H}\subseteq2^{\{1,2,\ldots,n\}}\) and
\(0\ne a_H\in \universe{Z}_m\)\@. We apply \emph{random restrictions}
independently to each variable \(x_i\), for \(i=1,2,\ldots,n\), in a
similar fashion to Ajtai \cite{cj95-02-2}, Furst, Saxe, and Sipser \cite{cj95-02-7}
and Razborov and Wigderson \cite{cj95-02-11}\@. Let
\[
\rho(x_i)=
  \condval{%
    0 & \mbox{with probability } 1-p \\
    \ast & \mbox{with probability } p
  }
\]
where \(\rho(x_i)=\ast\) means that \(x_i\) remains unrestricted, and
\(p=(1/2)n^{-1/2}\)\@.
%
\apar{Proof of Theorem 2-2}
For every \(c>0\) and \(\setsize{H}\geq(c/2)\log n\),
\begin{aequation}{2}
\Pr\left(\prod_{i\in H}\rho(x_i)\ne0\right)\leq
  p^{\frac{c}{2}\log n}\leq n^{-\frac{c}{4}\log n}
\end{aequation}
\sentence
Suppose that \(\setsize{\setofset{H}}\), the size of
\(\polynomial{P}\), satisfies \(\setsize{\setofset{H}}\leq
n^{\varepsilon\log n}\), for a small enough \(\varepsilon>0\)\@. Then,
because of (2), the degree of the polynomial after the restriction
will be small with high probability:
%
\[\Pr\bigl(\deg(\polynomial{P}\funccomp\rho)<(c/2)\log n\bigr)=1-\orderlt{1}\]
%
while \(\polynomial{P}\funccomp\rho\) still represents the
\(\function{OR}\) of at least \(\sqrt{n}\) variables with probability
\(1-\orderlt{1}\)\@. So, from (1), setting
\(c=\bigl(1/(q-1)-\orderlt{1}\bigr)\), where \(q\) is the smallest
prime divisor of \(m\), we arrive at a contradiction\@.
%
\apar{Proof of Theorem 2-3}
Part 2 can be proved in similar fashion, using inequality (1) with
\(r\geq 2\) instead of \(r=2\)\@. The details are left to the
reader\@.
%
{\samepage\markendlst{Proof of Theorem 2}}
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{3}{}
\prooffontshape
%
Let 
\[
\polynomial{P}(x_1,x_2,\ldots,x_n)=
  \sum_{H\in\setofset{H}}a_H\prod_{i\in H}x_i
\]
be a \(\umod m\) polynomial, weakly representing \(f_n\)\@. We apply
random restrictions independently to each variable
\(x_i\), for \(i=1,2,\ldots,n\), as in the proof of Theorem~2, or as
in \cite{cj95-02-2}, \cite{cj95-02-7}, or \cite{cj95-02-11}\@. Let
\[
\rho(x_i)=
  \condval{%
    0 & \mbox{with probability }(1-p)/2 \\
    1 & \mbox{with probability }(1-p)/2 \\
    \ast & \mbox{with probability }p
  }
\]
where \(p=(2\ln h)/h\)\@. Then, as in the proof of Theorem~2, or
as in the proof of Theorem 3 in \cite{cj95-02-11}, if
\[\setsize{\setofset{H}}\leq n^{\varepsilon\log n}\]
for a sufficiently small \(\varepsilon>0\), then
\begin{aequation}{3}
\Pr\bigl(\deg(\polynomial{P}\funccomp\rho)<
  \lfloor(1/3)\log h\rfloor\bigr)\geq 1-\orderlt{1}
\end{aequation}
while
\[
\Pr\left(\logiciterxor_{k=1}^{h}\rho(x_{ijk})\mbox{ is a constant}
 \right)=(1-p)^{h}\leq{1/h^{2}}
\]
\sentence
So, from (3) we conclude that---after fixing some more
variables---there exists a \(\umod m\) polynomial that weakly
represents \(\function{GIP}_{l,k}\) with degree less  than
\(\lfloor(1/3)\log h\rfloor\), and this contradicts our
Theorem~1\@.
%
{\samepage\markendlst{Proof of Theorem 3}}
\end{alabsubtext}
%
\asection{5}{Acknowledgments} 
%
\apar{5-1}
The author is indebted to David Barrington and to G\'abor Tardos for
discussions on this subject, and to Alexander Razborov, who directed
the author's attention to the random restriction techniques\@.
%
\end{articletext}
%
\begin{articlebib}
%
\bibliographystyle{\the\rbibstyle} 
\bibliography{cj95-02} 
%
\end{articlebib}
%
\end{document}