The Chinese Remainder Theorem states that a positive
integer $m$ is uniquely specified by its remainder modulo
$k$ relatively prime integers $p_1,\ldots,p_k$, provided
$m < \prod_{i=1}^k p_i$. Thus the residues of $m$ modulo
relatively prime integers $p_1 < p_2 < \cdots < p_n$
form a redundant representation of $m$ if $m < \prod_{i=1}^k p_i$
and $k < n$. This gives a number-theoretic construction of
an ``error-correcting code''
where a ``message'' (integer)
$m< \prod_{i=1}^k p_i$, is encoded by the list of its residues
modulu $p_1,\ldots,p_n$.
By the Chinese Remainder Theorem, if a code-word is corrupted
in $e < \frac{n-k}{2}$ coordinates, then there exists a unique
integer $m$ whose corresponding code-word differs from the corrupted
word in at most $e$
places. Furthermore, Mandelbaum~\cite{Mandelbaum76,Mandelbaum78} shows how
$m$ can be recovered efficiently given the corrupted word.
In this work we describe an efficient decoding algorithm for the
case in which the error $e$ is larger than $\frac{n-k}{2}$.
Specifically, given $n$ residues $r_1,\ldots,r_n$ and an
agreement parameter $t$,
we find a {\em list of all integers\/} $m < \prod_{i=1}^k p_i$
such that $(m~\mod p_i) = r_i$ for at least $t$ values of
One consequence of our result is a strengthening
of the relationship between average-case complexity of
computing the permanent and its worst-case complexity.
Specifically we show that if a polynomial time algorithm
is able to guess the permanent of a random $n\times n$ matrix
on $2n$-bit integers modulo a random $n$-bit prime
with inverse polynomial success rate, then
$\p^{\sharpp} = \bpp$.
Previous results of this nature typically worked over a fixed
prime moduli or assumed
success probability very close to one (as opposed to bounded
away from zero).
The Chinese Remainder Theorem states that a positive
integer $m$ is uniquely specified by its remainder modulo
$k$ relatively prime integers $p_1,\ldots,p_k$, provided
$m < \prod_{i=1}^k p_i$. Thus the residues of $m$ modulo
relatively prime integers $p_1 < p_2 < \cdots < p_n$
form a redundant representation of $m$ if $m < \prod_{i=1}^k p_i$
and $k < n$. This gives a number-theoretic construction of
an ``error-correcting code''
where a ``message'' (integer)
$m< \prod_{i=1}^k p_i$, is encoded by the list of its residues
modulu $p_1,\ldots,p_n$.
By the Chinese Remainder Theorem, if a code-word is corrupted
in $e < \frac{n-k}{2}$ coordinates, then there exists a unique
integer $m$ whose corresponding code-word differs from the corrupted
word in at most $e$
places. Furthermore, Mandelbaum~\cite{Mandelbaum76,Mandelbaum78} shows how
$m$ can be recovered efficiently given the corrupted word.
In this work we describe an efficient decoding algorithm for the
case in which the error $e$ is larger than $\frac{n-k}{2}$.
Specifically, given $n$ residues $r_1,\ldots,r_n$ and an
agreement parameter $t$,
we find a {\em list of all integers\/} $m < \prod_{i=1}^k p_i$
such that $(m~\mod p_i) = r_i$ for at least $t$ values of
One consequence of our result is a strengthening
of the relationship between average-case complexity of
computing the permanent and its worst-case complexity.
Specifically we show that if a polynomial time algorithm
is able to guess the permanent of a random $n\times n$ matrix
on $2n$-bit integers modulo a random $n$-bit prime
with inverse polynomial success rate, then
$\p^{\sharpp} = \bpp$.
Previous results of this nature typically worked over a fixed
prime moduli or assumed
success probability very close to one (as opposed to bounded
away from zero).
The Chinese Remainder Theorem states that a positive
integer m is uniquely specified by its remainder modulo
k relatively prime integers p_1,...,p_k, provided
m < \prod_{i=1}^k p_i. Thus the residues of m modulo
relatively prime integers p_1 < p_2 < ... < p_n
form a redundant representation of m if m <= \prod_{i=1}^k p_i
and k < n. This suggests a number-theoretic construction of
an ``error-correcting code'' that has been implicitly considered
often in the past. In this paper we provide a new algorithmic
tool to go with this error-correcting code: namely, a
polynomial-time algorithm for error-correction. Specifically, given
n residues r_1,...,r_n and an agreement parameter
t, we find a list of all integers m < \prod_{i=1}^k p_i
such that (m mod p_i) = r_i for at least t values of
i in {1,...,n}, provided t = Omega(sqrt{kn (log p_n)/(log p_1)}).
We also give a simpler algorithm, that has a nearly linear
time implementation, to decode from a smaller
number of errors, i.e.,
when t > n - (n-k)(log p_1)/(log p_1 + \log p_n).
In such a case there is a unique integer which has such
agreement with the sequence of residues.
One consequence of our result is that is a strengthening
of the relationship between average-case complexity of
computing the permanent and its worst-case complexity.
Specifically we show that if a polynomial time algorithm
is able to guess the permanent of a random n x n matrix
on 2n-bit integers modulo a random n-bit prime
with inverse polynomial success rate, then #P=BPP.
Previous results of this nature typically worked over a fixed
prime moduli or assumed very small (though non-negligible) error probability
(as opposed to small but non-negligible success probability).
The Chinese Remainder Theorem states that a positive
integer m is uniquely specified by its remainder modulo
k relatively prime integers p_1,...,p_k, provided
m < \prod_{i=1}^k p_i. Thus the residues of m modulo
relatively prime integers p_1 < p_2 < ... < p_n
form a redundant representation of m if m <= \prod_{i=1}^k p_i
and k < n. This suggests a number-theoretic construction of
an ``error-correcting code'' that has been implicitly considered
often in the past. In this paper we provide a new algorithmic
tool to go with this error-correcting code: namely, a
polynomial-time algorithm for error-correction. Specifically, given
n residues r_1,...,r_n and an agreement parameter
t, we find a list of all integers m < \prod_{i=1}^k p_i
such that (m mod p_i) = r_i for at least t values of
i in {1,...,n}, provided t = Omega(sqrt{kn (log p_n)/(log p_1)}).
We also give a simpler algorithm to decode from a smaller
number of errors, i.e.,
when t > n - (n-k)(log p_1)/(log p_1 + \log p_n).
In such a case there is a unique integer which has such
agreement with the sequence of residues.
One consequence of our result is that is a strengthening
of the relationship between average-case complexity of
computing the permanent and its worst-case complexity.
Specifically we show that if a polynomial time algorithm
is able to guess the permanent of a random n x n matrix
on 2n-bit integers modulo a random n-bit prime
with inverse polynomial success rate, then #P=BPP.
Previous results of this nature typically worked over a fixed
prime moduli or assumed very small (though non-negligible) error probability
(as opposed to small but non-negligible success probability).
The Chinese Remainder Theorem states that a positive
integer m is uniquely specified by its remainder modulo
k relatively prime integers p_1,...,p_k, provided
m < \prod_{i=1}^k p_i. Thus the residues of m modulo
relatively prime integers p_1 < p_2 < ... < p_n
form a redundant representation of m if m <= \prod_{i=1}^k p_i
and k < n. This suggests a number-theoretic construction of
an ``error-correcting code'' that has been implicitly considered
often in the past. In this paper we provide a new algorithmic
tool to go with this error-correcting code: namely, a
polynomial-time algorithm for error-correction. Specifically, given
n residues r_1,...,r_n and an agreement parameter
t, we find a list of all integers m < \prod_{i=1}^k p_i
such that (m mod p_i) = r_i for at least t values of
i in {1,...,n}, provided t = Omega(sqrt{kn (log p_n)/(log p_1)}).
We also give a simpler algorithm to decode from a smaller
number of errors, i.e.,
when t > n - (n-k)(log p_1)/(log p_1 + \log p_n).
In such a case there is a unique integer which has such
agreement with the sequence of residues.
One consequence of our result is that is a strengthening
of the relationship between average-case complexity of
computing the permanent and its worst-case complexity.
Specifically we show that if a polynomial time algorithm
is able to guess the permanent of a random n x n matrix
on 2n-bit integers modulo a random n-bit prime
with inverse polynomial success rate, then #P=BPP.
Previous results of this nature typically worked over a fixed
prime moduli or assumed very small (though non-negligible) error probability
(as opposed to small but non-negligible success probability).
