\documentstyle[11pt,titlepage]{article}

% REVISED VERSION
% Date: Thu, 19 Aug 1993 23:32 EST

% DINA4-Format
\oddsidemargin 6pt\evensidemargin 6pt\marginparwidth 48pt\marginparsep 10pt
\topmargin -18pt\headheight 12pt\headsep 25pt\footheight 12pt\footskip 30pt
\textheight 625pt\textwidth 431pt\columnsep 10pt\columnseprule 0pt
\sloppy
\newenvironment{rem}{\vspace{3mm}\noindent{\bf Remark. }}{\vspace{3mm}}
\newenvironment{claim}{\vspace{3mm}\noindent{\bf Claim. }}{\vspace{3mm}}
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Cor}[Theorem]{Corollary}
\newtheorem{Def}[Theorem]{Definition}
\newtheorem{Prop}[Theorem]{Proposition}

\newcommand{\theorem}[1]{\begin{Theorem} #1 \end{Theorem}}

\newcommand{\theoremcite}[2]{\begin{Theorem}{\rm\cite{#1}}~~#2
\end{Theorem}}

\newcommand{\proof}[1]{ \noindent {\it Proof.}
#1 \mbox{}\vspace{\baselineskip}\mbox{}\hfill$\Box$}

\newcommand{\proofof}[2]{ \noindent {\it Proof of #1.}
#2 \mbox{}\vspace{\baselineskip}\mbox{}\hfill$\Box$}

\newcommand{\lemma}[1]{\begin{Lemma}  #1 \end{Lemma}}

\newcommand{\cor}[1]{\begin{Cor}  #1 \end{Cor}}
\newcommand{\defi}[1]{\begin{Def}  #1 \end{Def}}

\newcommand{\deficite}[2]{\begin{Def}{\rm\cite{#1}}~~#2
\end{Def}}

\newcommand{\Pe}{{\rm P}}
\newcommand{\NP}{{\rm NP}}
\newcommand{\FP}{{\rm FP}}
\newcommand{\PH}{{\rm PH}}
\newcommand{\CH}{{\rm CH}}
\newcommand{\Mod}{{\rm Mod}}
\newcommand{\ModPH}{\mbox{\rm ModPH}}
\newcommand{\ModPHex}{{\scriptstyle\rm ModPH}}
\newcommand{\ModPex}{{\scriptstyle\rm ModP}}
\newcommand{\ModkP}{\mbox{\rm Mod$_k\Pe$}}
\newcommand{\ModpP}{\mbox{\rm Mod$_p\Pe$}}
\newcommand{\ModkPex}{{\scriptstyle\rm Mod\mbox{$\scriptscriptstyle _k$}P}}
\newcommand{\ModqPex}{{\scriptstyle\rm Mod\mbox{$\scriptscriptstyle _q$}P}}
\newcommand{\ModkprimePex}{{\scriptstyle\rm Mod\mbox{$\scriptscriptstyle _{k'}$}P}}
\newcommand{\AmpMP}{{\rm AmpMP}}
\newcommand{\PP}{{\rm PP}}
\newcommand{\MP}{{\rm MP}}
\newcommand{\num}{{\rm\#}}
\newcommand{\numP}{{\rm\#\Pe}}
\newcommand{\ParP}{{\mbox{$\oplus$\Pe}}}

\newcommand{\pttredu}{\mathrel{\hbox{$\leq_{\rm tt}^{\rm p}$}}}
\newcommand{\pcttredu}{\mathrel{\hbox{$\leq_{\rm ctt}^{\rm p}$}}}
\newcommand{\pdttredu}{\mathrel{\hbox{$\leq_{\rm dtt}^{\rm p}$}}}
\newcommand{\pmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm p}$}}}
\newcommand{\ptredu}{\mathrel{\hbox{$\leq_{\rm T}^{\rm p}$}}}


% \newcommand{\ParPex}{{\scriptstyle \oplus\Pe}}
% \newcommand{\ParPexex}{{\scriptscriptstyle \oplus\Pe}}

% From Jim Royer --KWR
% The following is a terrible hack, but it works---usually.
\newcommand{\parityP}{{\mathchoice{\raisebox{1pt}{$\displaystyle\oplus$}{\rm
   P}}{\raisebox{1pt}{$\textstyle\oplus$}{\rm
P}}{\raisebox{1pt}{$\scriptstyle\oplus$}{\rm
P}}{\raisebox{1pt}{$\scriptscriptstyle\oplus$}{\rm P}}}}

\newcommand{\BPP}{{\rm BPP}}
%\newcommand{\pair}[2]{\langle #1,#2\rangle}
%\newcommand{\triple}[3]{\langle #1,#2,#3\rangle}
\newcommand{\tuple}[1]{\mathopen{\langle}#1\mathclose{\rangle}}
\newcommand{\nat}{\mbox{$\cal N$}}

\newcommand{\CgP}{\mbox{${\rm C}_={\rm P}$}}
\newcommand{\CgPex}{\mbox{$\scriptstyle{\rm C}_={\rm P}$}}

\newcommand     {\nule}         {\{0,1\}}
\newcommand     {\x}            {(|x|)}

\newcommand{\AND}{\; \wedge \;}
\newcommand{\implies}{\Longrightarrow}
\newcommand{\into}{\rightarrow}


\makeatletter
\newcommand{\niceonespacing}

{\let\CS=\@currsize\renewcommand{\baselinestretch}{11}\tiny\CS}
\newcommand{\nicetwospacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}
{1.2}\tiny\CS}
\newcommand{\nicethreespacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}
{1.3}\tiny\CS}
\makeatother


\begin{document}

\title{The Power of the Middle Bit of a \#P Function
\footnote{ Preliminary versions of this work appeared in the
{\it Proceedings of the Fourth Italian Conference on Theoretical
Computer Science}, World Scientific, (1992), 317-329, and {\it
Proceedings of the Seventh Annual Conference on Structure in
Complexity Theory}, IEEE Computer Society Press, (1992), 111-117.
}\\
{\small (Revised Version)}}

\author{
Frederic Green\thanks{Clark University, Dept.\ of
Math/CS, Worcester, MA 01610.  Research partially
supported by a grant from the Direcci{\'o}n General de
Investigaci{\'o}n Cient{\'\i}fica y T{\'e}cnica
(DGICYT), Spanish Ministry of Education, while the
author was visiting the U. Polit{\`e}cnica de Catalunya,
Barcelona.}\\
\normalsize
Clark University\\
\and
Johannes K\"obler\thanks{Universit\"at Ulm, Theoretische
Informatik, Oberer Eselsberg, D-89069 Ulm, Germany.}
\thanks{
This research was supported by the DAAD (Acciones
Integradas 1991, 313-AI-e-es/zk).}\\
\normalsize
Universit\"at Ulm\\
\and
Kenneth W. Regan
\thanks{
SUNY/Buffalo, Computer Science Department, Buffalo, NY
14260. Supported by NSF Grant CCR-9011248.}\\
\normalsize
SUNY/Buffalo\\
\and
Thomas Schwentick
\thanks{
Universit{\"a}t Mainz, Institut f{\"u}r Informatik,
D-55099 Mainz, Germany.}\\
\normalsize
Universit{\"a}t Mainz\\
\and
Jacobo Tor\'an \thanks{ U. Politecnica de Catalunya,
Departamento L.S.I., Pau Gargallo 5, E-08028 Barcelona,
Spain.  Research partially supported by ESPRIT-II Basic
Research Actions Program of the EC under Contract No.
3075 (project ALCOM).}
\footnotemark[3]\\
\normalsize
U. Politecnica de Catalunya\\ }

\maketitle

\nicetwospacing

\begin{abstract}

This paper studies the class $\MP$ of languages which can
be solved in polynomial time with the additional
information of one bit from a $\#$P function $f$.
The middle bit of $f(x)$ is shown to be as powerful as any other
bit, whereas the $O(\log n)$ bits at either end are apparently weaker.
The polynomial hierarchy and the classes
\ModkP, $k\geq2$, are shown to be low for $\MP$.
They are also low for a class we call $\AmpMP$ which is defined
by abstracting the ``amplification'' methods of Toda
({\it SIAM J. Comput.} {\bf 20} (1991), 865--877).
%
% and that a wide range of bits around the middle
% have the same power.  By contrast, the $O(\log n)$ many
% least significant bits are equivalent to $\parityP$
% {\cite{BG92}}, and by a simple corollary to the result
% that PP is closed under polynomial-time $O(\log
% n)$-Turing reductions {\cite{BRS91}}, the $O(\log n)$
% many most significant bits are equivalent to PP; hence
% these bits are probably weaker.
% We study also the subclass $\AmpMP$ of languages whose $\MP$
% representations can be ``amplified,'' and show that 
% $\BPP^\parityP\subseteq\AmpMP$, and that important
% subclasses of $\AmpMP$ are low for $\MP$.
%
Consequences of these results for circuit complexity 
are obtained using the concept of a MidBit gate, which is defined to take
binary inputs $x_1,\dots,x_w$ and output the 
$\lfloor\log_2(w)/2\rfloor^{\rm th}$ bit in the binary
representation of the number $\sum_{i=1}^w x_i$. 
Every language in ACC can be computed by a family
of depth-2 deterministic circuits of size $2^{(\log
n)^{O(1)}}$ with a MidBit gate at the root and AND-gates
of fan-in $(\log n)^{O(1)}$ at the leaves. This result
improves the known upper bounds for the class ACC.
\end{abstract}

\section{Introduction}

The %recent%
celebrated results of Toda \cite{Toda} have sparked
renewed interest in the complexity classes $\numP$ \cite{Valiant},
PP (probabilistic polynomial time \cite{Gill}), and 
$\parityP$ (parity polynomial time \cite{PaZa,GoPa}).
One relationship among these classes is that
$\parityP$ comprises exactly those languages which are
decided with the information in the
rightmost bit of a $\numP$ function $f$, 
and PP, those decided with the information in the leftmost bit.
(For the latter statement we arrange, as described later, that binary
values $f(x)$ are padded with leading 0's out to a length
which depends only on $|x|$.)
Toda's two main theorems are that the polynomial-time hierarchy (PH)
is contained in $\BPP^{\parityP}$, and that the evidently larger class
$\PP^{\parityP}$ is contained in $\Pe^{\numP}$.
%
% randomly reduces to $\parityP$ (with bounded two-sided error),
% and that PP$^{\parityP}$ (the class defined by reductions to
% $\parityP$ with {\it un\/}bounded error) is contained in
% P$^{\numP}$.
The observation which inspired the present work is that in
Toda's proof of the second result, the full power of
P$^{\numP}$ is not needed.  Namely, the P$^{\numP}$
machine $M$ in the proof makes only one query $x$ to its oracle
$f \in \numP$, and furthermore the machine's decision
depends on only one bit of the answer $f(x)$ in binary notation.
%
% (Here $x$ can be the same as the input to $M$, or $f$ can be fixed
% as the $\numP$-complete function $\#$SAT and $M$ computes
% some other string in deterministic polynomial time as its query.)
Hence it is natural to ask which other languages can be decided
by looking at just one bit of a $\numP$ function.  
The class of languages with this property is defined by:

\begin{Def}\label{MPdef}
A language $L$ is in \MP\ if there exists a $\numP$ function $f$
and a polynomial-time computable function $g$
such that for all $x$,
$x\in L \Leftrightarrow (\lfloor f(x)/2^{g(x)}\rfloor \bmod 2) = 1$.
\end{Def}

Put another way, $x \in L$ iff there is a 1 at position $g(x)$
in the standard binary representation of $f(x)$.  
We call $g$ a {\em bit-selection function\/}.
The ``M'' stands for ``middle bit,'' since we show,
by judicious padding of values $f(x)$ to odd length,
that $g$ can be the function which indexes the
middle bit of the binary representation of $f(x)$.
In Section~3 we establish some basic properties of the class \MP,
including that \MP\ is closed downward under polynomial-time
many-one reductions and has complete problems.
% The closure of $\MP$ under polynomial-time truth-table reductions
% is P$^{\numP[1]}$, and under polynomial-time Turing reductions,
% is the same as P${PP}$ and P$^{\numP}$.

One motivation for studying \MP\ is that very little is known
about the structure of classes in the neighborhood of P$^{\numP}$,
even under relativizations.  Indeed, it is not even known whether
there exists an oracle set $A$ for which
PP$^{\parityP^A} \neq {\rm PSPACE}^A$; hence no $A$ for which
P$^{\numP^A[1]} \neq {\rm PSPACE}^A$
%
% or P$^{\numP^A} \neq {\rm PSPACE}^A$
%
is known either.  One surprising property of P$^{\numP[1]}$
which follows from the proof of Toda's theorem is that a rich
array of languages $A$ are {\em low\/} for the class, meaning that
P$^{\numP^A[1]} = $ P$^{\numP[1]}$. The main result of this
paper is that all of the languages that are known to be low
for P$^{\numP[1]}$ are also low for the possibly smaller class
MP. As shown in Section~4, the class $\BPP^{\parityP}$ from
Toda's first theorem is low for MP.
In proving these lowness results, we interpret the
familiar probability amplification in Toda's first theorem as a
means of inserting many 0's to the {\em right\/} of the important
bit, and the novel ``amplifying polynomials'' in his second
theorem as a means of inserting 0's to the {\em left\/} of that
bit. We abstract these two properties to define the subclass
$\AmpMP$ of MP languages whose representations in Definition
\ref{MPdef} can be transformed to insert any desired number of 0's
on both the left and the right of the selected bit. We show that
any class $\cal C \subseteq \AmpMP$ which is closed under both
$\pcttredu$ and $\pdttredu$ (that is, under polynomial-time conjunctive
and disjunctive truth-table reducibilities, respectively) is low
for both $\MP$ and for $\AmpMP$ itself. It follows that if $\MP =
\AmpMP$, or even if $\CgP \subseteq \AmpMP$, then the entire {\em
counting hierarchy\/} \cite{Wagner} collapses to MP.
We had hoped to be able to show lowness without any extra
closure conditions on $\cal C$.  However, very recently
K\"obler and Toda \cite{KT} showed that if the class 
$\AmpMP$ defined in this paper is low for MP, then the
counting hierarchy likewise collapses.
We return to this question and give other open problems
about MP in our concluding Section~7.

While it is immediate that $\parityP \subseteq$
MP, it is not obvious {\em {\`a} priori} that Mod$_3$P
$\subseteq$ MP, since in order to decide whether a number
written in base 2 is congruent to 0 modulo 3, one needs the
information of all of its bits.  Nevertheless, in Section~5 we show
that for all $k \geq 2$, all languages in Mod$_k$P (see
{\cite{CaHe2,Hert,BG92}}) are low for $\MP$.
% as are the languages
% which randomly reduce with bounded 2-sided error to Mod$_k$P. 
Sections~5 and~6 together present our main
application, which is an improvement on previous simulations of
the circuit class ACC (originally defined by Barrington
\cite{Barrington}).

Some background and explanation of how our work
builds on prior techniques is in order. It is by now well known
that relationships among
% relativized and unrelativized
Turing machine classes,
both with and without relativization, 
correspond closely to circuit simulations or circuit-class separations.
Toda proved his first theorem, PH$ \subseteq $BP$ \cdot \parityP$,
using techniques introduced by Valiant and Vazirani \cite{VV}.
The circuit analogue of this result was proved by Allender \cite{Allender},
using polynomial methods introduced by Razborov \cite{Raz87}
and Smolensky \cite{Smo87}. It states that
any AC$^0$ predicate is computed with high probability by a family
of circuits of {\em quasi-polynomial\/} size (i.e., size $2^{(\log
n)^{O(1)}}$) which consist of a parity gate connected to AND gates
which are {\em small\/}  (i.e., have polylog fan-in).
Allender and Hertrampf \cite{AlHe} subsequently applied
the Valiant-Vazirani technique
to obtain a uniform version of Allender's result.

Yao \cite{Yao} then used these techniques to obtain
the first non-trivial upper
bound for ACC.  By combining the Valiant-Vazirani method with
improved versions of Toda's ``amplifying polynomials,''
he showed that every language in ACC is recognized by a
family of depth-2 probabilistic circuits of quasipolynomial size
%
% $2^{(\log n)^{O(1)}}$
%
with a symmetric gate at the root and small AND gates
%
% of fan-in $(\log n)^{O(1)}$
%
at the leaves.
Then Beigel and Tarui
\cite{BeTa} simplified Yao's proof and strengthened the result in two
respects:
(1) 
the circuits given by Yao can be
made deterministic without increasing their size, and
(2) the simulation applies not only to ACC circuits, but also to
circuits consisting of one symmetric gate (at the root)
connected to ACC subcircuits.
This is the circuit analogue
of the result that PH and all the Mod$_k$P classes are
low for P$^{\numP[1]}$,
and shows that this lowness relationship holds relative to
all oracles.

In the results of both
\cite{Yao} and \cite{BeTa}, the
symmetric gate at the root depends on the number of
inputs and the types of modular gates used in the ACC
circuit.  It seems very hard to work directly with
depth-2 circuits of the type given in
\cite{Yao} or \cite{BeTa} in proving lower bounds,
since all that can be said about
the gates at the root is that they belong to an infinite
subfamily of the symmetric functions.  Our improvement is
that such circuits
can be restricted to have a symmetric gate of type
MidBit at the root and still have the power of ACC.  A MidBit gate
over $w$ inputs $x_1,\dots,x_w$ is a gate which outputs the value
of the $\lfloor\log_2(w)/2\rfloor^{\rm th}$ bit in the binary
representation of the number $\sum_{i=1}^wx_i$. 
Let the term MidBit$^+$ refer to families
of depth-2 deterministic circuits of quasipolynomial size
%
%$2^{(\log n)^{O(1)}}$
%
with a MidBit gate at the root and
small AND-gates at the leaves (see Definition 6.2).
Our result is that ACC circuits
% and the more-general kind of
% circuits with a topmost symmetric gate in (2) above,
can be simulated by MidBit$^+$ circuits.
Furthermore, as follows from our lowness results,
even a circuit consisting of a Midbit of ACC
circuits can be simulated by MidBit$^+$ circuits. 
Much of the above
%could be done
can be proved by applying the ideas and
techniques of \cite{BeTa}.  Our main technical contribution
regarding the ACC problem is a means of converting representations
involving counting modulo some prime $p$ into
``Midbit'' representations in binary notation.
%
% MidBit of Mod$_p$ gates (for $p$ prime) can be simulated
% by a MidBit$^+$ circuit. This same technique is used to
% prove our lowness results.
% 
By multiplying by a carefully
chosen number which is not too large, the rightmost
``bit" of a number written in base $p$ can be
represented as a single bit in the middle of a binary
string (Lemma~\ref{iso_b}). By choosing an appropriate Toda
polynomial, the bit can be ``isolated" from the rest of
the string, and this leads to our
Theorem~\ref{modlow}, and in circuit form,
Theorem~\ref{lowpoly}.

Yao \cite{Yao} conjectured that there are languages in TC$_0$
which cannot be computed by probabilistic
circuits consisting of a symmetric gate over small
AND's, and Beigel and Tarui \cite{BeTa} make a similar,
nominally weaker conjecture for deterministic circuits of
this kind. Likewise, we believe that there are TC$_0$
languages that cannot be computed by MidBit$^+$
circuits. The study of these circuits may therefore
provide a way to show that TC$_0$ is not contained in ACC.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Preliminaries and Notation}\label{pre}
All languages considered here are over the alphabet
$\Sigma=\{0,1\}$. The length of a string $x\in\Sigma^*$
is denoted by $|x|$.  If $n$ is a natural number, $|n|$
denotes the length of its binary encoding, namely
$|n|=\lceil\log_2(n+1) \rceil$.
For a set~$A$, $|A|$
denotes its cardinality.  The characteristic function of
a set $A$ is denoted by $\chi_A$.  The set
$\{0,1,2,\dots\}$ of non-negative integers is denoted by
$\nat$.
We fix some standard means of injectively encoding sequences 
$(x_1,\dots x_k)$ of strings, where $k > 0$ is arbitrary,
by single strings $\tuple{x_1,\dots,x_k}$,
such that $|\tuple{x_1,\dots,x_k}|$ depends only on
$\sum_{i=1}^k |x_i|$, and both the encoding and decoding are
computable in polynomial time.
Where intent is clear we write $f(x_1,\dots,x_k)$ or
$\chi_A(x,y)$ in place of
$f(\tuple{x_1,\dots,x_k})$ or $\chi_A(\tuple{x,y})$.

% This paper does not require a tupling function which is surjective---it
% suffices that the range of $\tuple{\dots}$ belongs to $\Pe$.
% This allows us for instance to say that a two-argument function $f$
% belongs to $\numP$ if the function $f'(z)$, defined to be
% $f(x,y)$ if $z = \tuple{x,y}$ and 0 otherwise, belongs to $\numP$.

We write $\FP$ for the class of deterministic polynomial-time
computable functions.  To every polynomial-time bounded
nondeterministic Turing machine (NTM) we 
associate the {\em counting function\/}
$\#acc_N(x)$, defined to be the number of accepting computations
which $N$ has on input $x$.  
The class of such functions is denoted by $\numP$.
%
% More generally, for any complexity class $\cal C$, $\#\cal C$ denotes
% the class of functions $f: \Sigma^* \rightarrow \nat$
% such that for some polynomial $p$ and language $A \in \cal C$,
% and all $x \in \Sigma^*$, 
% $f(x) = |\{y \in \Sigma^*: |y| \leq p(|x|) \AND \tuple{x,y} \in A\}|$.
%
A language $L$ belongs to the class PP if there is an NTM $N$ with polynomial
time bound $p$ such that for all $x$,
$x \in L$ iff $\#acc_N(x) > 2^{p(|x|) - 1}$.
For any natural number $k \geq 2$, 
$L$ belongs to the class Mod$_k$P
if there exist $N$ and $p$ such that for all $x$,
$x \in L$ iff $\#acc_N(x) \not\equiv 0$ (mod $k$).
With $k = 2$ we have $x \in L$ iff $\#acc_M(x)$ is odd,
and this class is called $\parityP$ (``parity-P'').

 It is well-known that $\numP$ is closed not only under addition
and multiplication but also under summation of exponentially many
$\numP$ functions and multiplication of polynomially many $\numP$
functions. That is, if $f(\cdot,\cdot)$ is in $\numP$ and $p$ is a
polynomial, then the functions $\sum_{y, |y| \le p(|x|)} f(x,y)$
and $\prod_{m \le p(|x|)} f(x, 0^m)$ are also in $\numP$.

An oracle machine $M$ may have a function $f$
instead of a language as its oracle.
$M$ is {\em nonadaptive\/}
%
% (see \cite{LadnerLynchSelman})
%
if for every computation path leading up to some query $z$,
the set of possible next queries does not depend on the answer $f(z)$.
Otherwise $M$ is {\em adaptive\/}.
The class of languages (respectively, functions) computed by
such machines $M$ with an oracle from some class $\cal C$ 
is denoted by $\Pe_{tt}^{\cal C}$
(respectively, $\FP_{tt}^{\cal C}$).
%
% ; the subscript $tt$ stands for ``truth-table reduction.''
%
When $M$ is deterministic and nonadaptive, and accepts iff
at least one of its queries is answered ``yes''
(respectively, iff all of its queries are answered ``yes''),
$M$ is said to compute a polynomial-time {\em disjunctive\/}
(resp.\ {\em conjunctive\/}) truth-table reduction, and the
corresponding reducibility relations are denoted by
$\pdttredu$ and $\pcttredu$.
Finally, given $k > 0$, a relativizable language class $\cal C$, and a 
class $\cal D$ of either languages or functions,
${\cal C}^{{\cal D}[k]}$ is the class of all languages in
${\cal C^{\cal D}}$ witnessed by a machine of type ${\cal C}$
which asks at most $k$ queries on every computation
path; these queries may be adaptive.
The class $\cal D$ is {\em low\/} for $\cal C$ if
the class ${\cal D}$, when used as an oracle for
${\cal C}$, does not increase the power of $\cal C$,
that is, $\cal C^{\cal D} = \cal C$. Further information on
these concepts may be found in \cite{badiga1,sch}.

\section{Bits of {\#P} Functions and Counting Classes}
\label{sec:Count}
If a given pair of functions $f \in \numP$ and $g \in \FP$ satisfy
Definition~\ref{MPdef} for some language $L$, then we say
{\em $L \in \MP$ via $f$ and $g$}.
For visual convenience we also use a second representation
which involves a {\em bounding polynomial\/}
for $f$, meaning a polynomial $p$ such that
for all $x$, $f(x) < 2^{p(|x|)}$.
Then $f(x)$ is written as
a binary string of length exactly $p(|x|)$, using leading 0's if necessary,
with the least significant bit numbered 0 and written rightmost, and the most
significant bit numbered $p(|x|)-1$.
As noted in Section~1, PP consists of
the languages decided by the leftmost bit under this representation,
and $\parityP$, those decided by the rightmost bit.
The name $\MP$ comes from our first result, which shows
that all languages $L \in \MP$ have MP-representations by which
membership of $x$ in $L$ is decided by the middle bit.

\begin{Prop}\label{MP=midbit}
Let $L \in \MP$.  Then there is a $\numP$ function $f$
such that for all $x$, $|f(x)|$ is odd, and $x \in L$
iff the middle bit of $f(x)$ is a $1$.  Furthermore, the index
of the middle bit is given by a polynomial in $|x|$ alone.
\end{Prop}

\proof{
Take $f_0 \in \numP$ and $g \in \FP$ such that $L \in \MP$ via
$f_0$ and $g$, and let $p$ be a bounding polynomial for $f_0$.
Let $p$ be a bounding polynomial for $f$.
Then we may also suppose without loss of generality that
for all $x$, $g(x) \leq p(|x|)$. Then the function $f$ defined by
$f(x) = 2^{2p(|x|)}+2^{p(|x|)-g(x)}f_0(x)$ belongs to $\numP$.
Since for all $x$, $f_0(x) < 2^{p(|x|)}$, we have
$f(x) < 2^{2p(|x|)+1}$, and so $|f(x)|=2p(|x|)+1$.
(Thus no leading 0's are needed.)
The bit of $f_0(x)$ originally selected by $g(x)$ is now in
position $p(|x|)$, which is the middle bit of $f(x)$.
}

We note that in this and later proofs, in place of asking for one bit
of the constructed $\numP$ function $f$ evaluated on the input $x$,
one can ask for the same bit of the $\numP$-complete function
\#SAT evaluated at some other argument $y=h(x)$ where $h$ is a
polynomial-time computable polynomially honest function. The next
result implies that, modulo the belief that PP and $\parityP$ are
proper subclasses of  $\Pe^{\numP[1]}$, the bits at distance
$O(\log n)$ (where $n = |x|$) from either the left or right end of
\#SAT are easier than the middle bit (this follows easily from
known results).  On the other hand, it is possible to push the
decision bit of any MP language quite close to either end of the
binary string representing $f(x)$, in comparison with the
length of $f(x)$. That is, for any $L \in $MP, for any $\epsilon
> 0$, there is a $\numP$ function $f$ such that the deciding bit for
$x \in L$ is as close as $|f(x)|^{\epsilon}$ to either end of the
binary representation of $f(x)$. In this sense, a wide range of
bits around the middle are equally as powerful as the middle bit.
 

% while those that are
%at distance $\Omega(n^{\epsilon})$ from either end are
%equally as hard as the middle bit.
%(Note: Here the length $m$ of the
%representation of $f(x)$ is given by a fixed polynomial in $n$, and
%hence the asymptotic expressions  $O(\log n)$ and $\cup_{\epsilon >
%0} \Omega(n^{\epsilon})$ in the last statement are the same with
%$m$ in place of $n$.)

\begin{Prop}\label{compare-bits}
\mbox{}
\begin{itemize}
\item[(a)]
Let $L$ be in $\MP$ via a function $f\in\#\Pe$ and a bit
selection function $g\in\FP$.
If $g(x) = O(\log(|x|))$, then $L \in \parityP$, while
if $|f(x)| - g(x) = O(\log(|x|))$, then $L \in \PP$.
\item[(b)]
Let $L \in \MP$.  Let $0 < \epsilon < 1$, and let $g$ be a
polynomial-time computable function which takes a string $x$
and a number $m$ as arguments, such that always
$m^{\epsilon} < g(x,m) < m - m^{\epsilon}$.
Then there exists a $\numP$ function $f'$ with bounding polynomial $p'$
such that upon taking $g'(x) = g(x,p'(|x|))$ as bit-selection function,
$L \in \MP$ via $f'$ and $g'$.
\end{itemize}
\end{Prop}

\proof{
(a)~The statement for $\parityP$ is immediate from \cite{BG92}.
The statement for $\PP$ follows quickly from the result
$\Pe^{\PP[O(\log n)]} = \PP$ in \cite{BRS91}:
Let $c$ be a constant such that $|f(x)|-g(x)\leq
c\log_2(|x|)$ for all $x\in\Sigma^*$. Then
$f(x)<2^{g(x)+c\log_2(|x|)}$, and the bits at the
positions $g(x)+c\log_2(|x|)-1,\dots,g(x)$ in the binary
representation of $f(x)$ can be computed in polynomial
time by binary search asking $c\log_2(|x|)$ many queries
to the \PP\ oracle set $\{\langle x,i\rangle\mid f(x)\geq i\}$.

(b)~Let $f$ and the middle-bit selector $p$ be as in
Proposition~\ref{MP=midbit}, and let
$p'(n) = (p(n)+2)^{\lceil 1/\epsilon \rceil}$.  With $g'$ as given in
the statement of this proposition, define $f'(x) = 2^{p'(n) - 1} +
2^{g'(x)-p(n)}f(x)$, where $n = |x|$. Then bit number $p(n)$ of
$f(x)$ is the same as bit number $g'(x)$ of $f'(x)$.  Because $g'$
is in $\FP$ and $g'(x) > p'(n)^{\epsilon} \geq p(n)$, $f'$ is in
$\numP$. Hence $f'$ and $g'$ form an $\MP$ representation for $L$.
(Note that $p'$ also serves as a bounding polynomial for $f'$.)
}

\noindent
% Note also that $p'$ serves as a bounding polynomial for $f'$,
% since $|f'(x)| = g'(x)-p(n)+|f(x)| = g'(x)+p(n)+1
% < p'(n) - p'(n)^{\epsilon} + p(n) + 1 \leq p'(n)+1$,
With $m = p'(n)$, the
selected bit may be as low as $m^{\epsilon}$ or as high as
$m - m^{\epsilon}$, depending only on $g$.
We do not have any quantitative results on the difficulty of the bits
in positions between $O(\log n)$ and $m^{\epsilon}$.
Next we collect some basic structural properties of MP.

\begin{Prop} \label{basics} \mbox{}
\begin{itemize}
\item[(a)]
$\PP^{\parityP} \subseteq \MP \subseteq\Pe^{\numP[1]}$.

\item[(b)]
$\MP$ has complete sets under $\pmredu$.

\item[(c)]
$\MP$ is closed downward under $\pmredu$, and is closed under complements
and join. 

\item[(d)]
$\MP = \Pe^{\MP[1]}$.
\item[(e)]
$\MP$ is closed under intersection if and only if\/
$\MP=\bigcup_{k\geq1}\Pe^{\MP[k]}$.
\end{itemize}
\end{Prop}

\proof{
(a)~The inclusion $\PP^{\parityP} \subseteq \MP$ follows
from inspection of Toda's proof \cite{Toda} that
$\PP^{\parityP} \subseteq \Pe^{\numP}$, as discussed in
Section~1.  The inclusion
$\MP \subseteq \Pe^{\numP[1]}$ is obvious.

(b)~The language $U_{\MP}=\{\langle
N,x,0^k,0^m\rangle\mid$ $N$ is a nondeterministic TM and
there is a 1 at position $k$ in the binary
representation of the number of all accepting paths of
length $\leq m$ of $N$ on input $x\}$ is easily seen
to be complete for \MP\ under $\pmredu$.
Complete languages based on counting satisfying assignments to
Boolean formulas can also be defined.

(c)~Let $B$ be in $\MP$ via some $f_B \in \numP$ and
$g\in\FP$, and suppose that
$A\pmredu B$ via some $\FP$ function $h$.  Then 
the function $f_A = f_B \circ h$ is in $\numP$,
and the function $g\circ h$ is in FP. 
For all $x\in\Sigma^*$, $x\in A$ if and only if there is
a 1 at position $g(h(x))$ in the binary representation
of $f(h(x))$, so $A\in \MP$.

For complements, consider the function $f'(x)=f(x)+2^{g(x)}$,
which belongs to $\numP$ and flips the bit at position
$g(x)$ in the binary
representation of $f(x)$.
Given $A,B \in \MP$ with $\numP$ functions $f_A$ and $f_B$
respectively, the join $0A \cup 1B$ is represented by the $\numP$
function $f$ defined by
$f(0x) = f_A(x)$, $f(1x) = f_B(x)$.

(d)~This holds for any class which contains $\Pe$ and has
the closure properties in (c).

(e)~Likewise, since \MP\ contains $\Pe$ and is closed under $\pmredu$,
it follows (see \cite{ksw}) that
$\bigcup_{k\geq1}\Pe^{\MP[k]}$ coincides with the
Boolean closure of \MP, which equals $\MP$ iff \MP\ is closed under
intersection.  }

Finally we compare the polynomial-time Turing and truth-table closures
of $\MP$.

\begin{Prop}\label{ttclosures} \mbox{}
\begin{itemize}
\item[(a)]
$\Pe^{\MP} = \Pe^{\PP} = \Pe^{\numP}$.
\item[(b)]
$\FP_{tt}^{\MP}=\FP_{tt}^{\numP}=\FP^{\numP[1]}$.
\item[(c)]
$\Pe_{tt}^{\MP}=\Pe^{\numP[1]}$.
\end{itemize}
\end{Prop}

\proof{
Part (a) is obvious, and (c) follows immediately from (b).
The first equality in (b) follows from the fact that the
value of a $\numP$ function can be computed in
polynomial time by asking nonadaptive queries to an \MP\
oracle. The second equality, namely that a round of
nonadaptive queries to a $\numP$ oracle function can be
simulated by one query to a $\numP$ oracle function, is
shown in \cite{CaHe1}.
}

Fortnow and Reingold \cite{FoRe91} proved that PP is closed downward
under polynomial-time truth-table reductions ($\pttredu$).
Since their result relativizes, the class
$\PP^{\parityP}$ is also closed downward under $\pttredu$.
Hence if $\MP = \PP^{\parityP}$, then both
classes equal $\Pe^{\numP[1]}$.  The open problems of whether
$\MP = \PP^{\parityP}$ or whether $\MP$ is closed under intersection
are discussed at the end of the paper.
 

\section{The Class AmpMP}

In this section we introduce a subclass $\AmpMP$ of
$\MP$ that will be very useful in obtaining lowness results
for a variety of complexity classes including
$\parityP$, $\BPP$, $\PH$, and $\ModkP$, $k\geq2$.
Toda's proof, which as mentioned in
Proposition~\ref{basics}(a) yields
$\PP^{\parityP}\subseteq \MP$, actually shows that
languages $L$ in $\PP^{\parityP}$ have
$\MP$-representations of a special kind.  Namely, for every polynomial $r$,
there is a $\numP$ function $f$ such that for all $x$,
not only does the middle bit of
$f(x)$ equal 1 iff $x \in L$, but also the $r(|x|)$
bits to the left of this bit are always 0.  We call
this property ``amplification on the left of the
decision bit.''  As noted below, familiar
probability-amplification methods for languages $L$ in BPP 
yield $\numP$ functions which allow 0's to be inserted to the
{\em right\/} of the bit $\chi_L(x)$.
When the construction implicit in the whole
of Toda's paper is carried out on a language $L$ in the polynomial
hierarchy (more precisely, to $L$ in $\BPP^{\parityP}$),
any desired number $m$ of 0's (bounded by a polynomial in $|x|$)
can be inserted on {\it both} the left and the right of the
decision bit. This motivated us to study the class of all
languages with this amplification property, and to call
the class $\AmpMP$.

\begin{Def} \label{ampmp}
A language $L$ is in $\AmpMP$ if there are functions $f \in \numP$
and $u \in \FP$ such that for all
$x\in\Sigma^*$ and $m>0$ there exist nonnegative
integers $a$ and $b$ with $b < 2^{u(x,0^m)}$ such that
\[
f(x,0^m)=a2^{u(x,0^m)+2m+1}+\chi_L(x)2^{u(x,0^m)+m}+b.
\]
\end{Def}

\noindent
Put another way, $L$ is in $\AmpMP$ if there are
functions $f \in \numP$ and $u,v\in\FP$ such
that for every $x\in\Sigma^*$ and $m>0$, the binary
representation of $f(x,0^m)$ is of the form
%
\begin{equation}\label{AmpMPrep}
a_{v(x,0^m)-1}\dots a_0\,\underbrace{0\,\dots\,0}_{m \rm\
times}\,\chi_L(x)\,\underbrace{0\,\dots\,0}_{m \rm\
times}\, b_{u(x,0^m)-1}\dots b_0.
\end{equation}
%
We say the functions $f, u, v$ form an AmpMP
representation of $L$. Here and later, it is understood
that $a_{v(x,0^m)-1}\dots a_0$ and $b_{u(x,0^m)-1}\dots
b_0$ are strings which may depend on $x$ and $m$; only
their lengths and not their actual values matter.

\begin{Prop}\label{BPPlow}
$\BPP$ and $\parityP$ are subclasses of $\AmpMP$.
\end{Prop}

\proof{
Let $L \in \BPP$.
The standard method for reducing the error probability to
$2^{-(m+1)}$ (see e.g.\ \cite{Schoning})
takes the majority result of $O(m)$ trials.
Making $m$ a second argument yields a $\numP$ function
$f(x,0^m)$ and a polynomial $p(n,m)$ with the following property:
Whenever $x \in L$, $f(x)$ in binary begins with $1^{m+1}$
(or equals $2^{p(n,m)}$),
and when $x \notin L$, $f(x)$ begins with $0^{m+1}$.
Then the function $f'(x,0^m) = f(x,0^m) + 2^{p(n,m)-(m+1)}$
belongs to $\numP$ and has the
decision bit $\chi_L(x)$ in position $p(n,m)$, followed 
by $0^m$ to its right.
Since $\chi_L(x)$ is the leading bit, this satisfies
Definition \ref{ampmp} with $a = 0$.

Given $L \in \parityP$, Toda's amplifying polynomials yield a
$\numP$ function $f$ such that for all $x$ and $m$,
if $x \in L$ then $f(x,0^m) \equiv 0$ (mod $2^m$), and if
$x \notin L$, then $f(x,0^m) \equiv -1$ (mod $2^m$) (see \cite{Toda}). 
Defining $f'(x,0^m) = 2^m(f(x,0^{m+1})+1)$ then places
$0^m$ on the right as well as the left of the bit
$\chi_L(x)$. }

It follows by bit-shifting methods similar to those
of Proposition \ref{MP=midbit} that
every $\AmpMP$ language $L$ has a representation as
in~(\ref{AmpMPrep}) above, in which $u$ and $v$ are polynomials in
$m$ and $|x|$. In fact, one can arrange that $v=u$, so that the
decision bit $\chi_L(x)$ is in the middle.  However, we prefer to
keep $v$ and $u$ separate.


\begin{Lemma}\label{closure}\mbox{}
\begin{itemize}
\item[(a)]
$\AmpMP$ is closed under complementation,
\item[(b)]
$\AmpMP$ is closed under intersection,
\item[(c)]
$\AmpMP$ is closed under bounded truth-table reductions.
\end{itemize}
\end{Lemma}

\proof{
(a) Let $L$ be in \AmpMP, and let $u,v \in \FP$ and
$f \in \numP$ provide the $\AmpMP$ representation as
in~(\ref{AmpMPrep}). Here and below we write $v$ and $u$ as short
for $v(x,0^m)$ and $u(x,0^m)$. Consider the function $f'(x,0^m)$
whose value in binary is \[ a_{v-1}\dots
a_0\,\underbrace{1\,\dots\,1}_{m \rm\
times}\,\chi_L(x)\,\underbrace{1\,\dots\,1}_{m \rm\ times}\,
b_{u-1}\dots b_0. \]
Since this equals $f(x,0^m)$ plus some powers of 2 determined by
$m$ and $u$ alone, $f'$ is in $\numP$.
Let $p'$ be a polynomial which bounds the running time of some
nondeterministic Turing machine $N$ whose counting function $\#acc_N$
is the same as $f'$. Then, by interchanging accept and reject states
in $N$, the function $f''(x,0^m) = 2^{p'(|\tuple{x,0^m}|)+1} - 1 -
f'(x,0^m)$ is also in $\numP$.  In $f''(x,0^m)$,  the complement of
the bit $\chi_L(x)$ is flanked by $m$ 0's.

(b) Let $L_1,L_2$ be two sets in \AmpMP, with respective
representations $f_1,u_1,v_1$ and $f_2,u_2,v_2$.  Then
$f_1(x,0^m)$ has the form
\[
a_{v_1 - 1}\dots a_0\,\underbrace{0\,\dots\,0}_{m
\rm\ times}\,\chi_{L_1}(x)\,\underbrace{0\,\dots\,0}_{m
\rm\ times}\, b_{u_1 - 1}\dots b_0.
\]
Let $h(x,0^m) = v_1(x,0^m) + 2m + 1 + u_1(x,0^m)$, which bounds
the length of $f_1(x,0^m)$.  Let $v'_2$ abbreviate $v_2(x,0^{h(x,0^m)})$,
and let $u'_2$ abbreviate $u_2(x,0^{h(x,0^m)})$.
Then $f_2(x,0^{h(x,0^m)})$ has the form
\[
a'_{v'_2 - 1}\dots
a'_0\,\underbrace{0\,\dots\,0}_{h(x,0^m) \rm\
times}\,\chi_{L_2}(x)\,\underbrace{0\,\dots\,0}_{h(x,0^m)
\rm\ times}\, b'_{u'_2 - 1}\dots b'_0,
\]
for some strings $a'$ and $b'$.  
The function $f_3(x,0^m) = f_1(x,0^m)\cdot f_2(x,0^{h(x,0^m)})$
also belongs to $\numP$.  Because of all the 0's
around the bit $\chi_{L_2}(x)$, the value
$\chi_{L_2}(x)\cdot f_1(x,0^m)$ appears as a substring of 
$f_3(x,0^m)$, and in particular, the decision bit
$\chi_{L_1}(x)\cdot \chi_{L_2}(x)$ for $L_1 \cap L_2$
appears at position
$u_1 + m + u'_2 + h(x,0^m)$.

(c)~Since by (a) and (b) $\AmpMP$ is closed under Boolean operations,
it suffices to show that $\AmpMP$ is closed under many-one
reductions.  Suppose $A \pmredu L$ where $L \in \AmpMP$.
Let $f$, $u$, and $v$ provide the representation as
in~(\ref{AmpMPrep}) for $L$, and let $t$ be the polynomial-time
computable function used  in the reduction.  Define the function 
$f'(x,0^m)=f(t(x),0^m)$. The value $f'(x, 0^m)$ has the form \[
a_{v(t(x),0^m)-1}\dots a_0\,\underbrace{0\,\dots\,0}_{m
\rm\ times}\,\chi_L(t(x))\,\underbrace{0\,\dots\,0}_{m
\rm\ times}\, b_{u(t(x),0^m)-1}\dots b_0.
\]
Then $\chi_L(t(x)) = \chi_A(x)$, and the functions
$u'(x,0^m) = u(t(x),0^m)$ and 
$v'(x,0^m) = v(t(x),0^m)$ complete an $\AmpMP$-representation for
$A$. }

The technical key to our lowness results is a lemma which shows
that the value of a function which is in $\numP$ with a bounded number
of queries to $\AmpMP$ can be obtained as a substring of the 
value of a function in $\numP$, with no queries.
By (c) above, for any $k > 0$, 
$\Pe^{\AmpMP[k]} = \AmpMP$.
Hence $\numP^{\AmpMP[k]} = \#\AmpMP$, where $\#\AmpMP$ equals the
class of functions $f$ such that for some language 
$A$ in $\AmpMP$ and polynomial $q$, and all $x \in \Sigma^*$,
%
\begin{equation}\label{numAmpMP}
f(x)=\sum_{y\in\{0,1\}^{q(|x|)}}\chi_A(x,y).
\end{equation}

\begin{Lemma}\label{midnump}
For every function $f \in \#\AmpMP$ there is a function
$f' \in \numP$ such that for all $x \in \Sigma^*$ and
$m \geq 0$, the binary representation of $f'(x,0^m)$ has the form
\[
a_{v-1}\dots a_0\,\underbrace{0\,\dots\,0}_{m \rm\
times}\,f(x)\,\underbrace{0\,\dots\,0}_{m
\rm\ times}\, b_{u-1}\dots b_0.
\]
% where $u$ and $v$ are polynomials in $|x|$ and $m$, and 
% the length of the string $f(x)$ is given by a polynomial in $|x|$.
\end{Lemma}

\noindent
As usual we suppose that $f(x)$ is written as a string of length
exactly $p(|x|)$, where $p$ is some bounding polynomial.
Then the above states that $\lfloor f'(x,0^m)/2^{u+m} \rfloor$
is congruent to $f(x)$ modulo $2^{p(|x|)+m}$.

\bigskip
\proof{
Given $f$, take $A \in \AmpMP$ and the polynomial $q$ from
(\ref{numAmpMP}).
By the remarks following Proposition \ref{BPPlow}, there are
polynomials $u,v$ and a $\numP$ function $f_A$ such that for all
pairs $\tuple{x,y} \in \Sigma^*$ and $k > 0$, the binary
representation of $f_A(\tuple{x,y},0^k)$ has the form
\begin{equation}\label{typo-mania}
a_{v(n',k) - 1}\dots a_0\,\underbrace{0\,\dots\,0}_{k \rm\ times}\,
\chi_A(x,y)\,\underbrace{0\,\dots\,0}_{k \rm\ times}\,
b_{u(n',k) - 1}\dots b_0,
\end{equation}
where $n' = |\tuple{x,y}|$.  
By our particular choice of tupling function in Section~\ref{pre},
and since $|y| = q(|x|)$,
$|\tuple{x,y}|$ depends only on $|x|$.
Thus the position of the bit $\chi_A(x,y)$ is the same for all $y$.
Now given $x \in \Sigma^n$ and $m \geq 0$, take $k = m+q(n)+1$, and
define
\[
f'(x,0^m) = \sum_{y \in \{0,1\}^{q(n)}} f_A(\tuple{x,y},0^k).
\]
Then $f' \in \numP$.  The binary representation of 
$f'(x,0^m)$ is obtained by summing the representations
in~(\ref{typo-mania}), and by Eq.~(\ref{numAmpMP}) and the choice of
$k$, $f(x)$ appears  as a substring of length exactly $q(n)+1$
flanked by $m$ 0's on both sides. (Also note $u$ and $v$ are
polynomials in $n$ and $m$.) }

\cor{\label{blow}\mbox{}
\begin{itemize}
\item[(a)]
$\bigcup_{k>1}\MP^{\AmpMP[k]} = \MP$.
\item[(b)]
$\bigcup_{k>1}\AmpMP^{\AmpMP[k]} = \AmpMP$.
\end{itemize}
}

\proof{
Given $L \in \MP^{\AmpMP[k]}$,
$L$ has a representing function $f \in \numP^{\AmpMP[k]}$.
Then the function $f'$ in
Lemma~\ref{midnump} provides an MP-representation for $L$---here $m$
is immaterial and can be fixed to 0.
For (b), if $f$ is an AmpMP-representation, then so is $f'$.
}

\noindent
The limitation of this corollary is that it only applies
to bounded truth-table reductions to $\AmpMP$.
To apply it for full Turing reductions, we seek technical
conditions on subclasses $\cal C$ of $\AmpMP$ under which 
any number of queries to $\cal C$ made by a nondeterministic
machine can be replaced by two queries.

\theorem{\label{condis}
Let $\cal C$ be a subclass of $\AmpMP$ which is closed downward under
both $\pcttredu$ and $\pdttredu$.  Then $\cal C$ is low
both for \MP\ and for \AmpMP.}

\proof{
Let $L \in \MP^A$ where $A \in \cal C$.  Let
$B = \{0\tuple{x_1,\dots,x_k} : \mbox{ each } x_i \mbox{ belongs to } A\}$,
and let 
$C = \{1\tuple{x_1,\dots,x_k} : \mbox{ some } x_i \mbox{ belongs to } A\}$.
By the closure properties of $\cal C$, $B$ and $C$ belong to $\cal C$,
and by the closure properties of $\AmpMP$, the language
$D = B \cup C$ belongs to $\AmpMP$.
Let $N$ be a
nondeterministic oracle TM such that the counting function
$\#acc_{N^A}(x)$ gives an $\MP$ representation for $L$.
By a standard trick, replace $N$ by a nondeterministic
OTM $N'$ which on any input $x$
guesses a computation path of $N(x)$ and also guesses the oracle
answers along the path.  Let $y_1,\dots,y_k$ denote the query
strings whose answers were guessed as ``yes'' along this path,
and $z_1,\dots,z_l$, those guessed ``no.''
Then this path by $N'$ accepts iff
$0\tuple{y_1,\dots,y_k} \in B$, 
$1\tuple{z_1,\dots,z_l} \notin C$, and the path guessed by $N$
accepts. $N'$ need make only two queries to its $\AmpMP$ oracle $D$,
and since this trick does not change the number of accepting
computations, Corollary \ref{blow} implies that $L \in \MP$.
The case $\AmpMP^A = \AmpMP$ is similar.
}


Since $\BPP$ and $\parityP$ are closed under polynomial-time
Turing reductions ($\ptredu$) \cite{Ko,PaZa}, 
it follows from Proposition \ref{BPPlow} and Theorem \ref{condis}
that they are low for both $\MP$ and $\AmpMP$.
We can quickly show the same lowness property for the class
$\BPP^{\parityP}$ shown in \cite{Toda} to contain the polynomial
hierarchy ($\PH$).

\begin{Prop}\label{BP+Plow}
$\BPP^{\parityP}$ and $\PH$ are low for $\MP$ and for $\AmpMP$.
\end{Prop}

\proof{
Proposition \ref{BPPlow} relativizes to show that for any oracle set $A$,
$\BPP^A \subseteq \AmpMP^A$.  Hence
$\BPP^{\parityP} \subseteq \AmpMP^{\parityP}$.  
Since $\parityP$ is low for $\AmpMP$, it follows that
$\BPP^{\parityP} \subseteq \AmpMP$. Since $\BPP^{\parityP}$ is
closed downward under $\ptredu$, it too is low for $\AmpMP$. 
Lowness for $\MP$ is similar, and the conclusions for $\PH$ follow
since $\PH \subseteq \BPP^{\parityP}$. }

 By careful examination of the proof in \cite{Toda}, we find 
that the lowness of $\BPP^{\parityP}$ for MP is a consequence of
the more general result that any $\numP^{\BPP^{\parityP}}$
function reduces to the ``middle bits" of some $\numP$ function
(see \cite{TodaWat} for related results about $\numP^{\PH}$).
Furthermore, the bits can be isolated any distance $m$ from the
left part of the string, independent of the input length $|x|$.

%
%A closer look at what actually happens in \cite{Toda} in
%regard to $\BPP^{\parityP}$ produces the following statement,
%whose point is that the polynomial $p$ concerned depends only on
%$|x|$ and not on $m$. 

\theorem{\label{BPP_Par}
For every function $f$ in $\numP^{\BPP^{\parityP}}$
there exist  a function $h\in\numP$ and a polynomial $p$
such that for all $x$ and $m$,
\[
f(x)\equiv \lfloor h(x,0^m)/2^{p(|x|)} \rfloor
\pmod{2^{m}}.
\]
}

\proof{
Let $f$ be in $\numP^{\BPP^{\parityP}}$.
Since $\Pe^{\BPP^{\parityP}} = \BPP^{\parityP}$, there exist a language
$A \in \BPP^{\parityP}$ and a polynomial $q$ such that
for all $x \in \Sigma^*$,
\[
f(x)=\sum_{y\in\{0,1\}^{q(|x|)}}\chi_A(x,y).
\]
By Proposition \ref{BPPlow} for $\BPP$ relativized to $\parityP$,
we obtain a function $f' \in \numP^{\parityP}$ and a polynomial $u$ such that
for all $x$ and $y$, the binary representation of
$f'(\tuple{x,y},0^m)$ has the form
\[
\chi_A(x,y)\,\underbrace{0\,\dots\,0}_{m \rm\
times}b_{u(|\tuple{x,y}|)-1}\dots b_0.
\]
For all $x$, with $n = |x|$, define
\[
g(x) = \sum_{y \in \{0,1\}^{q(n)}} f'(\tuple{x,y},0^{q(n)}).
\]
Because of
the choice $m = q(|x|)$, the sum of the $b_{u-1} \dots b_0$ terms does
not spill any carries into the sum of the $\chi_A(x,y)$ terms.
Since $|\tuple{x,y}|$ depends only on $n$ for $y \in \Sigma^{q(n)}$, there is
a polynomial $p(n)$ such that for all $x$, $g(x)$ has the form
\[
g(x) = f(x) b'_{p(|x|)-1}\dots b'_0.
\]
Now $g$ also belongs to $\numP^{\parityP}$.
Since $\Pe^{\parityP} = \parityP$,
there exists a language $B \in \parityP$
and a polynomial $r$ such that for all $x$,
\[
g(x)=\sum_{z\in\{0,1\}^{r(|x|)}}\chi_B(x,z).
\]
Next, by using Toda's amplifying polynomials as in the proof of 
Proposition \ref{BPPlow}, we obtain a function
$g' \in \numP$ such that for all $x,z \in \Sigma^*$ and $m \in \nat$,
\[
g'(x,z,0^m) \equiv \chi_B(x,z) \pmod{2^m}.
\]
Finally define
\[
h(x,0^m) = \sum_{z \in \{0,1\}^{r(|x|)}} g'(x,z,0^m).
\]
Then $h \in \numP$, and for all $x$ and $m$,
\[
h(x,0^m) \equiv g(x) \pmod{2^m}.
\]
The conclusion follows on noting that
$\lfloor g(x)/2^{p(|x|)} \rfloor = f(x)$.
}

\noindent
We return to this in connection with open problems about $\AmpMP$ 
in Section~7.
Before presenting our new idea which gives analogous lowness results for the
classes Mod$_k$P, $k \geq 3$, we observe one more consequence of the
results in this section. 

\begin{Prop}
If $\CgP \subseteq \AmpMP$, then $\CH = \MP$.
\end{Prop}

\proof{
Assume that $\CgP \subseteq \AmpMP$.  Since the class
$\CgP$ is closed under disjunctive and conjunctive
reductions ({\cite{Toran,GuNaWe,Green,BCO}}) it follows
from Theorem~\ref{condis} that $\CgP$ would be low for {\MP}.
However, from the result of \cite{Toran} that $\PP^{\PP} = \PP^{\CgPex}$,
this would give $\PP^{\PP} \subseteq \MP^{\CgPex} = \MP$,
implying that the entire counting hierarchy collapses to $\MP$.
}


\section{Lowness of Mod Classes for the Class MP}

In this section we show that for any $k$, Mod$_k$P is
low for {\MP} and $\AmpMP$.  The key to this result is
the following lemma, which says that the
``amplification'' of a $\numP$-function in $k$-adic
representation can, in some sense, be saved in dyadic
representation.

\lemma{\label{iso_b}
Let $k > 1$, let $f \in \numP$ with bounding polynomial $s$, and
let FP functions $q$ and $r$ be given such that for all $z$,
$2^{q(z)}$ and $k^{r(z)}$ are at most $2^{s(|z|)}$. For all $z$
write  $a(z) = \lfloor f(z)/k^{r(z)} \rfloor$ and $b(z) = f(z) \bmod
k^{r(z)}$. Suppose that for all $z$, $b(z) \leq
k^{r(z)}/2^{q(z)+1}$. Then there exist a $\numP$ function $h$, an
FP function $u$, and a  non-negative integer-valued function $a'$ 
such that for all $z$, %
\begin{equation}\label{goal}
h(z)=a'(z)a(z) 2^{u(z)+q(z)} + b(z) 2^{u(z)} + c(z),
\;\;\mbox{ where }\;\; c(z) < 2^{u(z)}.
\end{equation}
%
}

\proof{
We have that for all $z$, $f(z) = a(z)k^{r(z)} + b(z)$, where
$b(z) \leq k^{r(z)}/2^{q(z)+1}$.
We first claim that we can find 
$g \in \numP$, a polynomial $u$, and a function
$b': \Sigma^* \longrightarrow \nat$
such that for all $z$,
\[
g(z) = a(z)2^{u(z)} + b'(z),\;\;\mbox{ where }\;\;
b'(z) < 2^{u(z)-q(z)}.
\]
For all $z \in \Sigma^*$, let $u(z) = q(z)+s(z)+1$ and
$g(z) = f(z)\lceil 2^{u(z)} / k^{r(z)} \rceil$.
The quantity $\lceil 2^{u(z)} / k^{r(z)} \rceil$ is polynomial-time
computable, because the functions $u(z)$ and $r(z)$ are bounded
by a polynomial in $|z|$. Hence $g$ is in $\numP$.
%In
%the rest of the proof we write $u$, $q$, and $r$ as short for
%$u(|z|)$, $q(|z|)$, and $r(|z|)$.\footnote{ %
%I haven't done this, just in case the rest of you would rather
%stick to writing $u(|z|)$ etc.\ everywhere.
%I've put in the previous ``Note'' only because we, 
%under the influence of Referee A, seemed to miss this point
%that was unstated in our original submission.
%If the point seems clear without the note, we can take it out.
%I changed the earlier $p$ to $u$ for continuity with the 
%notation for $\AmpMP$---this appears to make 
%no difference for the notation in section 6.
%}

Clearly $g(z) \geq a(z)2^{u(z)}$.  Then
%
\begin{eqnarray*}
g(z) - a(z)2^{u(z)}\;&\leq\;&
f(z)\left(1 + \frac{2^{u(z)}}{k^{r(z)}}\right) - a(z)2^{u(z)}\\
&=& f(z) + (a(z)k^{r(z)} + b(z))\frac{2^{u(z)}}{k^{r(z)}} - a(z)2^{u(z)}\\
&=& f(z) + b(z)\frac{2^{u(z)}}{k^{r(z)}}\\
&<& 2^{s(z)} + 2^{u(z)-q(z)-1} = 2^{u(z)-q(z)}.
\end{eqnarray*}
%
The last line follows by $f(z) < 2^{s(z)}$, $b(z) \leq k^{r(z)}/2^{q(z)+1}$,
and the definition of $u$.
This proves the claim.
Now define
\[
h(z) = f(z)2^{u(z)} + g(z)i(z),
\]
where $i(z)$ is the unique integer which satisfies
$0\leq i(z) < 2^{q(z)}$ and
$i(z)\equiv -k^{r(z)}$ (mod $2^{q(z)}$).
Then it follows that
\begin{eqnarray*}
h(z)&=&a(z)k^{r(z)}2^{u(z)}+b(z) 2^{u(z)} + a(z)
2^{u(z)}i(z) + b'(z)i(z)\\
&=&a(z)2^{u(z)}[k^{r(z)}+i(z)]+b(z)2^{u(z)} +b'(z)i(z),
\end{eqnarray*}
where
$b'(z)i(z) < 2^{u(z)}$ and $k^{r(z)}+i(z)\equiv 0$ (mod $2^{q(z)}$).
}

\theorem{\label{modlow}
For every prime $k$, $\ModkP \subseteq \AmpMP$.
}

\proof{
Let $A$ be a set in $\ModkP$ and let $r$ be the FP function
$r(x, 0^m) = 2m + 2$, so that $k^{r(x, 0^m)}\geq 2^{2m+2}$.
%%such that for all $m$, $k^{r(m)}\geq2^{2m+2}$.
 Since $k$ is prime,
we can adapt results from
Toda~\cite{Toda} and Beigel and Gill \cite{BG92}
to obtain
a function $f_A \in \numP$ such
that for all $x$ and $m$,
\[
f_A(x,0^m) \equiv \chi_A(x) \pmod{k^{m}}.
\]
Now let $f(x,0^m) = f_A(x,0^{r(x,0^m)})\!\cdot\! 2^{m}$. Then $f \in
\numP$, and there is a function $a_0:\Sigma^*\rightarrow\nat$ such
that for all $x$ and $m$,
\[
f(x,0^m) = a_0(x,0^m)2^{m}k^{r(x,0^m)}+\chi_A(x)2^{m},
\]
where $\chi_A(x)2^{m}\leq k^{r(x,0^m)}/2^{m+2}$.  With reference
to the statement of Lemma \ref{iso_b} and the quantities $a(z)$ and
$b(z)$ in the proof, taking $z = \tuple{x,0^m}$, we have
$a(z) = a_0(x,0^m)2^m$, $b(z) = \chi_A(x)2^m$, and
$q(z) = m+1$.
Then Lemma \ref{iso_b} yields 
$h \in \numP$, a polynomial $u$, and $a',c:\Sigma^*\rightarrow\nat$
such that for all $x$ and $m$,
\[
h(x,0^m) = a'(x,0^m)a_0(x,0^m)2^m\cdot 2^{u(x,0^m)+m+1} + \chi_A(x)
2^{m+u(x,0^m)} + c(x,0^m),
\]
where $c(x,0^m) < 2^{u(x,0^m)}$.  In binary representation,
this places $m$ 0's on both the left and the right of the bit
$\chi_A(x)$.
}

\cor{\label{anyk}
For any $k\geq2$, \ModkP\ is low for {\MP} and for
\AmpMP.}

\proof{
First suppose $k$ is prime.  Then 
\ModkP\ is closed under $\ptredu$
{\cite{BG92}}.  Hence by Theorems \ref{condis} and \ref{iso_b},
\ModkP\ is low for {\MP} and for {\AmpMP}.
Now suppose $k$ is composite; then one can write
$k = p^{e}k'$ where $p$ is prime, $e \geq 1$, and
gcd$(p,k')=1$.  Then by the representation theorem of
Hertrampf \cite{Hert},
\[
\ModkP\subseteq\ModpP^{\ModkprimePex}.
\]
Since the above lowness proof for the prime case
relativizes, the lowness of \ModkP\ follows by iterating
this argument for all the prime factors of $k$.
}

The next statement follows quickly from the above by a
proof similar to that of Theorem \ref{BPP_Par}.

\cor{\label{low}
For any $k\geq2$ and every function $f$ in
$\numP^{\ModkPex}$ there exist a function $g\in\numP$ and
a polynomial $p$ such that for all $x$,
\[
f(x) \equiv \lfloor g(x,0^m)/2^{p(|x|+m)} \rfloor
\pmod{2^{m}}.
\]
}

As a side remark, let $\ModPH$ be the closure of $\Pe$ under the operations
$\cal C \mapsto \NP^{\cal C}$ and
$\cal C \mapsto \ModkP^{\cal C}$ for $k \geq 2$.
This is intuitively an extension of the polynomial hierarchy
by the $\ModkP$ classes, and can be regarded as the
polynomial-time analogue of the circuit class ACC.

\cor{
$\ModPH$ is low for {\MP} and for {\AmpMP}.  }

% \noindent
% We define a generalization of the polynomial time
% hierarchy that contains also Mod classes; it can be
% considered as the polynomial time analogue to the
% circuit class ACC.
% 
% \defi{
% $\ModPH$ is the smallest nonempty language class $\cal
% C$ that for any set $A$ in $\cal C$ contains the classes
% $\NP^A$ and $\ModkP^A$, $k\geq2$.}
% 
% \cor{
% $\ModPH$ is low for {\MP} and for {\AmpMP}.  }
% 
% \cor{\label{ModPH}
% For every function $f$ in $\numP^{\ModPHex}$ there exist
% a polynomial $p$ and a function $h$ in \numP\ such that
% \[\lfloor h(x,0^m) / 2^{p(|x|+m)}\rfloor \equiv f(x)
% \pmod{2^{m}}.\]
% }
 
\section{A New Upper Bound for ACC}

   The methods of the preceding section relativize. It
is thus not surprising that there are analogous circuit
results. In this section we prove them directly.  Our
main result in this section is that there is {\sl one
particular} symmetric function which, together with AND
gates of small fan-in, can capture all of ACC: namely,
the symmetric function which outputs the middle bit of
the sum of the inputs.

\defi{
   A {\sl MidBit} gate over $w$ inputs $x_1, ... , x_w$
is a gate which outputs the value of the $\lfloor
\log_2(w)/2
\rfloor^{\rm th}$ bit in the binary representation of the number
$\sum_{i=1}^w x_i$.  }

 A {\sl Mod$_k$} gate over $w$ inputs $x_1,...,x_w$ is
defined to output 1 if $\sum_{i=1}^w x_i \not \equiv 0
\pmod{k}$ and 0 otherwise.

In our simulations circuits consisting of a particular
gate over small AND gates arise frequently, so we
introduce the following notation.

\defi{Let $G$ be a Boolean gate. A family of circuits $\{C_n\}$ is
called a family of $G^+$ circuits if there is a
polynomial $p$ such that for each $n$, $C_n$ consists of
a gate of type $G$ at the root whose inputs are at most
$2^{p(\log n)}$ AND gates each of size at most
$p(\log n)$. A family of Boolean functions $\{f_n\}$
is computable by a family of $G^+$ circuits $\{C_n\}$ if
for each $n$, $f_n(x_1,...,x_n) = C_n(x_1,...,x_n)$.}

Note that we will always speak of families of MidBit$^+$
or Mod$_k^+$ circuits. Even when we refer to a
MidBit$^+$ or Mod$_k^+$ circuit individually, it should
be understood that what is meant is a member of a
particular family of such circuits.

  The following theorem gives the circuit analogue of
Corollary~\ref{low}. We find that for
any family of functions which can be expressed as sums of Mod$_k^+$
circuits, there is a family of low-degree polynomials
whose middle bits agree with the bits of the original
functions.

\theorem{\label{lowpoly}
Let $k$ be prime and let $\{b_n\}$ be a family of
functions such that there exists a polynomial $r$ where
for each $n$, $b_n$ is of the form $$b_n(x_1,...,x_n) =
\sum \limits_{i=1}^w c_i(x_1,...,x_n),$$ where each
$c_i$ is a Mod$_k^+$ circuit and $w \le 2^{r(\log n)}$.
Then for any polynomial $t$ there are polynomials $p$
and $q$ and a family of polynomials $\{h_n\}$ of degree
$p(\log n)$ such that for each $n$,
\[b_n(x_1,...,x_n)
\equiv \lfloor h_n(x_1,...,x_n)/ 2^{q(\log n)} \rfloor
\pmod{2^{t(\log n)}}.\] }
\proof{
This is similar to the proof of Theorem~\ref{modlow}. To
simplify notation, unless explicitly stated,
$p,p',q,r,s,$ and $t$ denote $p(\log n)$,
$p'(\log n)$,$q(\log n), r(\log n),$
$s(\log n),$ and $t(\log n)$, respectively. Also
denote any function $g$ of $x_1,...,x_n$ as $g(x)$.  We
have that each Mod$_k^+$ circuit $c_i$ outputs 1 if and
only if a certain sum $\sigma_i$ of AND-gates is nonzero
mod $k$.  (From an observation of Beigel and Gill
\cite{BG92}, without loss of generality $\sigma_i$ is
always 0 or 1 (mod $k$), by Fermat's little theorem.)
Note that we can think of each $\sigma_i$ as a
polynomial in $\{x_1,...,x_n\}$ of polylog degree. We
make use of polynomials of a type first constructed by
Toda~\cite{Toda} and successively improved
by~\cite{Yao,BeTa}.  The {\em modulus-amplifying}\/
polynomials $Q_d$ have the property that for every
$k\geq1$ and $X\geq0$,
\begin{eqnarray*}
X\equiv0\pmod{k}&\Rightarrow&Q_d(X)\equiv0\pmod{k^d}, \\
X\equiv1\pmod{k}&\Rightarrow&Q_d(X)\equiv1\pmod{k^d}.
\end{eqnarray*}
(The modulus-amplifying polynomials constructed by
Beigel and Tarui~\cite{BeTa} have degree $2d-1$.) Now it
follows that $$b_n(x) = \sum \limits_{i=1}^w
\left[{Q_d(\sigma_i)
\bmod k^d}\right].$$ We choose $d = p'(\log n)$ where
$p'$ is a polynomial such that $k^{p'} > 2^{r+t+2}$.
Then $b_n(x) \le 2^r < k^{p'}$.  Now the outer sum in
the equation above for $b_n$ is less than $k^{p'}$, so
the ``mod" can be moved outside:
$$b_n(x) \equiv
\left[\sum \limits_{i=1}^w {Q_{p'}(\sigma_i)}\right]
\pmod{k^{p'}}.$$
We write
$$f_n(x) = \sum \limits_{i=1}^w {Q_{p'}(\sigma_i)}.$$
Then
$$f_n(x) = a_n(x) k^{p'} + b_n(x)$$
for some $a_n(x)$. Note that for some
polynomial $s$, $f_n(x) < 2^s$. Also note that since
$\sigma_i$ is a polynomial of polylog degree, there is
some polynomial $p$ such that $f_n$ is a polynomial of
degree $p(\log n)$ in the variables $x_1,...,x_n$.
Define the degree $p(\log n)$ polynomial $h_n$ as
follows: $$h_n(x) =i(n)\left\lceil 2^q / k^{p'}
\right\rceil f_n(x) + 2^qf_n(x),$$ where $i(n) \equiv
-k^{p'}$ (mod $2^t$) and $q$ is a polynomial such that
$q\geq s+t+2$, following the proof of Lemma~\ref{iso_b}.
Analogously we find that $\lceil 2^q / k^{p'} \rceil f_n(x) =
a_n(x)2^q+b'_n(x)$, where $b'_n(x) < 2^{q-t-1}$. Hence
$$h_n(x) \equiv 2^qb_n(x) + i(n)b'_n(x)\pmod{2^{q+t}},$$
where $i(n)b'_n(x) < 2^{q-1}$. This completes the proof.
}

\cor{\label{lowmidbit}
Let $k$ be prime and $\{C_n\}$ be a family of circuits
where for each $n$, $C_n$ consists of a MidBit gate over
$2^{polylog}$ Mod$_k^+$ circuits. Then $\{C_n\}$ is
computable by a family of MidBit$^+$ circuits.  }
\proof{Each $C_n$ is the MidBit of a sum $b_n$ of Mod$_k^+$ circuits.
Using the previous theorem and adopting the notations of
the proof, we can find a family of polylog-degree
polynomials $\{h_n\}$ obeying
\begin{eqnarray}\label{eq1}
 h_n(x)&\equiv&2^q b_n(x) + c_n(x) \pmod{2^{q+t}}
\end{eqnarray}
for some $c_n(x) < 2^{q-1}$. Choose $t > r$.  We can
express $h_n$ (mod $2^{q+t}$) as a sum of non-negative
terms with coefficients $< 2^{q+t}$. This can further be
rewritten as a sum $h'_n(x)$ of AND gates by replacing
terms with coefficients $> 1$ by a sum of identical
terms with unit coefficients.  Reducing the right hand
side of the congruence~(\ref{eq1}) mod $2^{q+t}$, we
obtain $2^q(b_n(x)\bmod 2^t) + c_n(x)$.  Now the output
bit of $C_n$ is in position $\lfloor r/2
\rfloor$ of $b_n(x)$ and is therefore in position $q + \lfloor r/2 \rfloor$ of $
   h'_n(x)$.  We can multiply the sum by repeated
addition so that this is precisely the middle bit.  }

  We now turn our attention to MidBit gates at the root
and {\sl pure ACC} subcircuits \cite{Yao}. A family $\{C_n\}$ of
circuits belongs to pure-ACC if there is a fixed $m$ such that for
all $n$, every gate in $C_n$ is a Mod$_m$ gate. This theorem
as well as its proof is the circuit analogue of Corollary
\ref{anyk}.

\theorem{\label{pureACC}
   Let $\{C_n\}$ be a family of depth-$d$ circuits
consisting of a MidBit gate at the root and Mod$_m$
gates at remaining levels.  Then $\{C_n\}$ is computable
by a family of MidBit$^+$-circuits.  }
\proof{
Beigel and Tarui \cite{BeTa} have shown that a Mod$_m$
gate can be simulated by a ``stratified" circuit of
$\Mod_{k_1}, \Mod_{k_2}, ...,\Mod_{k_l}$ gates where
$k_1,k_2,...,k_l$ are the prime divisors of $m$, on
levels $1, 2,...,l$, respectively, and polylog fan-in
AND gates on the lowest level. They also showed that a
polylog-size AND of Mod$_k$ gates (for $k$ prime) can be
switched with the Mod$_k$'s to produce a Mod$_k^+$
circuit. Using these facts, Corollary~\ref{lowmidbit}
and an inductive argument as in the proof of Lemma 6 in
\cite{BeTa}, each layer of Mod$_{k_i}$ gates
can be ``absorbed" in the MidBit gate, and the resulting
polylog fan-in AND gates ``pushed" down to the leaves.
The resulting circuit is a MidBit$^+$ circuit.
} %proof

The following main theorem uses a combination of the
above results, techniques of Valiant and Vazirani
\cite{VV}, Toda \cite{Toda},
Allender and Hertrampf \cite{AlHe}, and the
lowness methods of Section~4.
It says that circuits consisting of a MidBit gate over ACC
subcircuits can be simulated by MidBit$^+$ circuits. The
proof is similar to those of Theorems 1 and 2 in \cite{BeTa}.

\theorem{
   Let $\{C_n\}$ be a family of depth-$d$ circuits of
size $2^{polylog(n)}$ consisting of a MidBit gate at the
root and Mod$_m$, AND, OR, and NOT gates at remaining
levels. Then $\{C_n\}$ is computable by a family of
MidBit$^+$-circuits.  }
\proof{
Let $C_n = 1$ iff the $\lfloor \log_2(s)/2 \rfloor^{\rm
th}$ bit of $S$ is 1, where $S= \sum_{i=1}^s c_i$, with
each subcircuit $c_i$ consisting of AND, OR, NOT, and
Mod$_m$ gates, and without loss of generality,
$s=2^{q(\log n)}$ where $q$ is a polynomial. The AND
and OR gates in each $c_i$ can be replaced by
probabilistic Mod$_m^+$ circuits with
polylog-many random bits, using the
techniques of \cite{VV} as applied by \cite{AlHe}.  By pushing the
AND-gates to the leaves, as in the preceding theorem,
$c_i$ can be simulated by a probabilistic circuit $c'_i$
comprised of Mod$_m$ gates and AND gates of polylog
fan-in at the lowest level, so that
Pr$[c'_i \neq c_i] \leq 2^{-q(\log n)-2}$.
It is possible to simulate $c_i$
with such a $c'_i$ using $t(\log n)$ random bits
where $t$ is a polynomial such that $t > q + 2$.  Let
$c''_i$ denote the sum of $c'_i$ over all possible
settings of the random bits of $c'_i$, and let $S' =
\sum_{i=1}^s (c''_i + 2^{t(\log n)-q(\log n)-2})$.
One can show that $S'=2^{t(\log n)}S + r$ where $r <
2^{t(\log n)}$. The output of the desired MidBit$^+$
circuit is the bit in position $\lfloor \log_2(s)/2
\rfloor + t(\log n)$ of $S'$.  }



\section{Conclusion and Open Problems}\label{conclusion}
The class $\MP$ is important not only for its role as
the implicit upper bound in Toda's proofs \cite{Toda},
but also for its place at the frontier
of counting classes whose relationships are not well
understood. We have established several properties of the class
which make it a natural and attractive object of study, and used
results about it to improve the known upper bounds on the
circuit class ACC.
The first open problem is whether one can construct an oracle
relative to which the inclusions in 
Proposition \ref{basics}(a) are proper.
It is not even known whether there exists an oracle $A$
such that $\PP^{\parityP^A}$ is different from PSPACE$^A$.

A second problem which seems amenable to attack is whether 
$\MP$ is equal to $\PP^{\parityP}$.  If so, then
by Proposition \ref{ttclosures},
both classes are equal to $\Pe^{\numP[1]}$.
Interestingly, we can entertain intuitive arguments both for
and against $\MP = \PP^{\parityP}$.
Let $L$ be in $\MP$ via the $\numP$ function $f$ and 
midbit-selecting polynomial $p$.  On the ``for'' side,
one can seek a probabilistic hashing construction
whose object is to divide the number of witnesses by $2^{-p(n)}$,
and try to prove a slight correlation between 
bit $p(n)$ of $f(x)$ being 1 and the reduced number of
witnesses being odd.
On the negative side,
%
% as remarked at the beginning of Section~\ref{ampmp},
% 
every language $L \in \PP^{\parityP}$
has an $\MP$ representation which allows 0's to be inserted
to the left of the bit $\chi_L(x)$, and it would be
noteworthy if every $\MP$ language
%
% (or some complete member)
%
had this property.
A sub-problem is whether $\MP$ is closed under intersection.
The direct attempt to solve this by writing polynomial equations,
after the fashion of the proof that
$\PP$ is closed under intersection \cite{BRS91}, leads to the
following purely numerical question, which we have
circulated among mathematicians.
(Say $x$ is {\em top modulo\/} $2^k$ if
$(x \bmod 2^k) \geq 2^{k-1}$.)

\begin{quote}
In terms of $k$, what is the minimum degree of an
integer-valued polynomial $p(x,y)$ such that for some
polynomial $t$ and all $x$ and $y$,
$p(x,y)$ is top modulo $2^{t(k)}$ $\iff$ both $x$ and
$y$ are top modulo $2^k$?
\end{quote}

\noindent
The simplest polynomial we know which satisfies this
congruence relation (with $t(k) = k$) is
$p(x,y) = {x \choose 2^{k-1}}{y \choose 2^{k-1}}{2^{k-1}}$.
A.~Odlyzko and M.~Coster [personal communication, 1991]
have found
solutions with degree and coefficient size that are smaller, but still
$2^{\Theta(k)}$. If such $p$ can be found
with degree polynomial in $k$, then $p$ can be written
as a polynomial-sized sum of small binomial coefficients
in $x$ and $y$, which can then be used in building
polynomial-time NTMs.  Then by 
``lining-up'' decision bits as in the proof of
Proposition~\ref{MP=midbit}, it would follow that \MP\ is closed under
intersection.  A similar congruence relation modulo
$2^k$ with the same open problem is
$p(x,y) = 0 \iff (x = 0 \AND y=0)$.

The remaining discussion is motivated by the
important general problem of comparing the power of
computing mod 2 versus computing mod $k$ for $k > 2$.
First, we ask whether the class $\MP$ remains the same when
values $f(x)$ are written in some other prime or composite base,
where the acceptance condition may be defined either as the
selected bit being a 1, or as its being nonzero.
If $\MP = \PP^{\parityP}$ then the answer is immediately yes, but
unconditionally we have not been able to extend the methods
of Section~5 to show this.
In view of the strong belief that the classes Mod$_k$P are
different for all different values of $k$, it would not seem
surprising if the answer were no.  

Second, it follows from the proof of Theorem \ref{BPP_Par}
(which is essentially Toda's proof) that languages
in $\BPP^{\parityP}$ enjoy a property which is somewhat stronger
than our definition of $\AmpMP$ in Section~4.

% Second, a closer look than Proposition \ref{BP+Plow} at what
% actually happens when the construction in Toda's paper \cite{Toda}
% is carried out on a language $L$ in $\BPP^{\parityP}$
% produces the following:

\begin{Prop}\label{BP+Pstronger}
For every language $L \in \BPP^{\parityP}$ there are functions
$f \in \numP$ and $u,v \in \FP$ such that for all $x \in \Sigma^*$
and $m_1,m_2 \in \nat$, $f(x,0^{m_1},0^{m_2})$ has the form
\begin{equation}\label{stronger-amp}
a_{v(x,m_1,m_2)-1}\dots a_0\,
\underbrace{0\,\dots\,0}_{m_1 \rm\ times}\,\chi_L(x)\,
\underbrace{0\,\dots\,0}_{m_2 \rm\ times}\,
b_{u(x,m_2)-1}\dots b_0.
\end{equation}
\end{Prop}

% \noindent
% What happens is essentially first, we can find $B \in \parityP$
% and a polynomial
% $p(n,m)$ such that for all $x$ and $m_2$,
% letting $W = \{0,1\}^{p(|x|,m_2)}$,
% $x \in A \implies \Pr_{y \in W}[\tuple{x,y} \in B] > 1 - 2^{-(m_2 + 1)}$,
% and
% $x \notin A \implies \Pr_{y \in W}[\tuple{x,y} \in B] < 2^{-(m_2 + 1)}$.
% Let $u(x,m_2) = p(|x|,m_2) - (m_2 + 1)$.
% Second, let $g \in \numP$ be such that for all $x$ and $y$,
% $\tuple{x,y} \in B \iff g(x,y) \mbox{ is odd}$.
% Use Toda's amplifying polynomials to raise the
% modulus to $m = m_1 + 1 + m_2 + u(x,m_2)$.
% This yields a $\numP$ function $h$ such that for all
% $x$, $y$, $m_1$, and $m_2$,
% $h(x,y,0^{m_1},0^{m_2}) \equiv \chi_B(x,y)$ (mod $2^m$).  Setting
% \[
% f(x,0^{m_1},0^{m_2}) = \left(\sum_{y \in W} h(x,y,0^{m_1},0^{m_2})\right)
% + 2^{u(x,m_2)}
% \]
% completes the proof.  The {\em point\/} here is that
% $u(x,m_2)$ is independent of $m_1$.

\noindent
The point is that $u(x,m_2)$ is independent of $m_1$.
Intuitively speaking,
this says that languages $L \in \BPP^{\parityP}$ have $\AmpMP$ representations
in which one can first amplify on the right of the bit $\chi_L(x)$,
fix the length of the ``garbage term'' $b$, and then amplify on the left
to insert as many 0's as desired.

However, we were unable to obtain this stronger amplification property
given $L \in \ModkP$, $k \geq 3$ (and $k$ prime).
In Theorem \ref{modlow}, the trick was to multiply
$f_A$ by $2^m$ to get $f$, and this makes it hard to
separate $m$ into $m_1$ and $m_2$.  Moreover, the
polynomial $u$ which bounds the length of the ``garbage term'' $c$
depends on a bounding polynomial for $f$, which in turn
depends on the number of 0's to be inserted on the left anyway.

The interest in whether these results can be improved
was heightened by recent work of one of the present authors
and Toda \cite{KT}.
They define a language $L$ to belong to the class
ModP if there are functions $f \in \numP$ and $g \in \FP$ such
that for all $x$, $g(x) = 0^p$ where $p$ is prime, and
$x \in L \iff f(x) \neq 0 \pmod{p}$.
Then they prove that $\mbox{ModP} \subseteq \AmpMP$ and that
$\Pe_{tt}^{\ModPex} = \Pe^{\numP[1]}$.  Hence if either
$\AmpMP$ or ModP is
%
% closed under $\pcttredu$, or is
%
low for $\MP$, then the counting hierarchy collapses to $\MP$.
This is fairly strong evidence that $\AmpMP$ itself is not
low for $\MP$, and that Theorem \ref{condis} cannot be improved
much further.
However, intuitively speaking, the proof in \cite{KT}
that a given language $L$ in ModP belongs to $\AmpMP$
first amplifies on the {\em left\/}
of the bit $\chi_L(x)$ (``Claim~1'' in \cite{KT}), and {\em then\/}
on the right (``Claim~2'').

We considered the stronger amplification property (\ref{stronger-amp})
in early work on this paper, but rejected it because
the simpler Definition \ref{ampmp} expedited our main results.
With (\ref{stronger-amp}) we were able to weaken the condition on the
class $\cal C$ in Theorem \ref{condis}
from closure under $\pcttredu$ and $\pdttredu$ to
closure under $\pmredu$.
This still does not achieve our desire for a natural structural
condition for a language to be low for $\MP$ (or for $\Pe^{\numP}$).
We leave as our final open problem the question of whether
the stronger amplification property does capture lowness for $\MP$,
or to the contrary,
whether the arguments of \cite{KT} can be applied to this case as well.
This last problem may seem very arcane, but the results of
\cite{KT} show that a slight technical distinction can make a
large difference in the power of a class, and we suspect
that at least some of the keys to unlocking the secrets of
counting classes may be concealed in problems like this one.


\paragraph{Acknowledgments}
We wish to thank V. Arvind, Jim Royer and Richard Beigel
for helpful discussions.
We also thank the anonymous referees for perceptive comments
on earlier drafts of this paper and for suggestions in
improving the exposition.

\begin{thebibliography}{1}

\bibitem[Al~89]{Allender}
{\sc E.~Allender,} A note on the power of threshold
circuits.  In {\it Proceedings of the 30th Symposium on
Foundations of Computer Science}, (1989), 580-584.

\bibitem[AlHe~90]{AlHe}
{\sc E.~Allender, U.~Hertrampf}, On the power of uniform
families of constant depth threshold circuits.  In {\it
Proceedings 15th Symposium on Mathematical Foundations
Computer Science, Lecture Notes in Computer Science 452},
(1990), 158-164.

\bibitem[BaDiGa~87]{badiga1}
{\sc J.L. Balc\'{a}zar, J. D\'\i az, J. Gabarr\'{o}},
{\em Structural Complexity I}.  Springer, 1987.

\bibitem[Ba~89]{Barrington}
{\sc D. Barrington}, Bounded-width polynomial-size
branching programs recognize exactly those languages in
NC$^1$.  In {\it Journal of Computer and System
Sciences} {\bf 38}, (1989), 150-164.

\bibitem[BeChOg~93]{BCO}
{\sc R.~Beigel, R.~Chang, and M.~Ogiwara,} A
relationship between difference hierarchies and
relativized polynomial hierarchies. In {\it Mathematical Systems
Theory} {\bf 26}, (1993) 293-310.

\bibitem[BeGi~92]{BG92}
{\sc R. Beigel and J. Gill.} Counting classes:
thresholds, parity, mods, and fewness.  In {\it Theoretical
Computer Science} {\bf 103}, (1992), 3-23.

\bibitem[BeReSp~91]{BRS91} %%%%%%%%%% UPDATE
%%% Anyone know anything about this?
{\sc R.~Beigel, N. Reingold and D. Spielman,} PP is
closed under intersection.  In {\it Proceedings of the
23rd ACM Symposium on the Theory of Computation}, (1991),
1-11. A journal version is to appear in {\it Journal of
Computer and System Sciences}.

\bibitem[BeTa~91]{BeTa}
{\sc R.~Beigel, J.~Tarui,} On ACC.  In {\it Proceedings
of the 32nd Symposium on Foundations of Computer
Science}, (1991), 783-792.

\bibitem[CaHe~89a]{CaHe1}
{\sc J.~Cai, L.~Hem\-a\-chan\-dra,} Enumerative Counting
is Hard. In {\it Information and Computation} {\bf 92(1)},
(1989), 34-44.

\bibitem[CaHe~89b]{CaHe2}{\sc J. Cai, L.A. Hemachandra,}
On the power of parity. In {\it Proceedings 6th
Symposium on Theoretical Aspects of Computer Science,
Lecture Notes in Computer Science 349}, (1989), 229-240.

\bibitem[FoRe~91]{FoRe91}
{\sc L. Fortnow and N. Reingold,} PP is closed under
truth-table reductions. In {\it Proceedings of the 6th
Annual Conference on Structure in Complexity Theory},
(1991), 13-15.

\bibitem[Gi~77]{Gill}{\sc J. Gill,} Computational
complexity of probabilistic Turing machines. In {\it
SIAM Journal on Computing} {\bf 6}, (1977), 675-695.

\bibitem[GoPa~86]{GoPa}{\sc L. Goldschlager, I. Parberry},
On the construction of parallel computers from various
bases of Boolean functions. In {\it Theoretical Computer
Science} {\bf 21}, (1986), 43-58.

\bibitem[Gr~93]{Green} %%%%%%%%%% UPDATE
{\sc F.~Green,} On the power of deterministic reductions
to $\CgP$. In {\it Mathematical Systems
Theory} {\bf 26}, (1993), 215-233.

\bibitem[GuNaWe~90]{GuNaWe}
{\sc T. Gundermann, N. Nasser, and G. Wechsung,} A
survey on counting classes. In {\it Proceedings of the 5th
Annual Conference on Structure in Complexity Theory},
(1990), 140-153.

\bibitem[He~90]{Hert}
{\sc U.~Hertrampf,} Relations among MOD-classes.  In
{\it Theoretical Computer Science} {\bf 74}, (1990), 325-328.

\bibitem[Ko~82]{Ko}
{\sc K.\ Ko,} Some observations on the probabilistic
algorithms and NP-hard problems.  In {\it Information
Processing Letters} {\bf 14}, (1982), 39-43.

\bibitem[K\"oScToTo~92]{KoScToTo}{\sc J. K\"obler,
U. Sch\"oning, J. Tor\'an, and S. Toda,} Turing Machines
with few accepting computations and low sets for PP.  In
{\it Journal of Computer and System Sciences} {\bf 44}, (1992),
272-286.

\bibitem[K\"oScWa 87]{ksw}{\sc J. K\"obler,
U. Sch\"oning, and K. W. Wagner.} The difference and
truth-table hierarchies of NP.  In {\it Theoretical
Informatics and Applications} {\bf 21(4)}, (1987),
419-435.

\bibitem[K\"oTo~93]{KT}{\sc J. K\"obler and
S. Toda,} On the power of generalized MOD-classes.  In
{\it Proceedings of the 8th Structure in Complexity
Theory Conference}, (1993), 147-155.

\bibitem[LLS~75]{LadnerLynchSelman}{\sc R. Ladner,
N. Lynch, and A. Selman,}
A comparison of polynomial time reducibilities.  In
{\it Theoretical Computer Science} {\bf 1}, (1975), 103-123.

\bibitem[PaZa~83]{PaZa}{\sc C. Papadimitriou, S. Zachos},
Two remarks on the power of counting. In {\it 6th GI
Conference on Theoretical Computer Science, Lecture
Notes in Computer Science 145}, (1983), 269-276.

\bibitem[Raz~87]{Raz87}{\sc A. Razborov},
Lower bounds for the size of circuits of bounded depth
with basis {$\{\wedge,\oplus\}$}. In {\it Math. Notes Acad. Sci. USSR\/}
{\bf 41(4)}, (1987), 333-338.

\bibitem[Sch~83]{Schoning} {\sc U. Sch\"oning},
A low and a high hierarchy within NP. In {\it Journal of
Computer and System Sciences} {\bf 27}, (1983), 14-28.

\bibitem[Sch\"o 86]{sch}{\sc U. Sch\"oning.}
{\em Complexity and Structure.} Springer-Verlag {\it
Lecture Notes in Computer Science} 211, (1986).

\bibitem[Smo~87]{Smo87} {\sc R. Smolensky},
Algebraic methods in the theory of lower bounds for 
Boolean circuit complexity.  In
{\it Proceedings of the 19th ACM Symposium on the Theory of Computation},
(1987), 77-82.

\bibitem[Tod 91]{Toda}{\sc S. Toda.}
PP is as hard as the polynomial-time hierarchy.  In {\it
SIAM Journal on Computing} {\bf 20}, (1991) 865-877.

\bibitem[ToWa 92]{TodaWat}
{\sc S. Toda and O. Watanabe,} Polynomial time 1-Turing
reducibility from \#PH to \#P.  In {\it Theoretical Computer
Science} {\bf 100}, (1992), 205-221.

\bibitem[Tor~88]{Toran} {\sc J. Tor\'an},
An Oracle Characterization of the Counting Hierarchy,
{\it Proceedings of the 3rd Annual Conference on
Structure in Complexity Theory}, (1988), 213-223.

\bibitem[Va~79]{Valiant}{\sc L.G. Valiant,}
The complexity of computing the permanent.  In {\it
Theoretical Computer Science} {\bf 8}, (1979), 189-201.

\bibitem[ValVaz~86]{VV}
{\sc L.~Valiant and V.~Vazirani}, NP is as easy as
detecting unique solutions. In {\it Theoretical Computer
Science} {\bf 47}, (1986), 85-93.

\bibitem[Wa~86]{Wagner}
{\sc K. Wagner}, The complexity of combinatorial
problems with succinct input representation.  In {\it
Acta Informatica} {\bf 23}, (1986), 325-356.

\bibitem[Yao~90]{Yao}{\sc A. Yao,}
On ACC and threshold circuits.  In {\it Proceedings of
the 31st Symposium on Foundations of Computer Science},
(1990), 619-627.

\bibitem[Za~82]{Zachos}{\sc S. Zachos,}
Robustness of probabilistic computational complexity
classes under definitional perturbations.  In {\it
Information and Control} {\bf 54}, (1982), 143-154.
\end{thebibliography}

\end{document}