Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #4 to TR98-062 | 27th August 1999 00:00

Chinese Remaindering with Errors Revision of: TR98-062

RSS-Feed




Revision #4
Authors: Oded Goldreich, Dana Ron, Madhu Sudan
Accepted on: 27th August 1999 00:00
Downloads: 1683
Keywords: 


Abstract:

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).


Revision #3 to TR98-062 | 18th June 1999 00:00

Chinese Remaindering with Errors Revision of: TR98-062





Revision #3
Authors: Oded Goldreich, Dana Ron, Madhu Sudan
Accepted on: 18th June 1999 00:00
Downloads: 1293
Keywords: 


Abstract:

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).


Revision #2 to TR98-062 | 8th February 1999 00:00

Chinese Remaindering with Errors Revision of: TR98-062





Revision #2
Authors: Oded Goldreich, Dana Ron, Madhu Sudan
Accepted on: 8th February 1999 00:00
Downloads: 1195
Keywords: 


Abstract:

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).


Revision #1 to TR98-062 | 22nd November 1998 00:00

Chinese Remaindering with Errors Revision of: TR98-062





Revision #1
Authors: Oded Goldreich, Dana Ron, Madhu Sudan
Accepted on: 22nd November 1998 00:00
Downloads: 1284
Keywords: 


Abstract:

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).


Paper:

TR98-062 | 28th October 1998 00:00

Chinese Remaindering with Errors





TR98-062
Authors: Oded Goldreich, Dana Ron, Madhu Sudan
Publication: 29th October 1998 09:12
Downloads: 1098
Keywords: 


Abstract:

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).


Comment(s):

Comment #1 to TR98-062 | 25th November 1998 09:52

Similar results Comment on: TR98-062





Comment #1
Authors: Gabriel Istrate
Accepted on: 25th November 1998 09:52
Downloads: 723
Keywords: 


Abstract:




ISSN 1433-8092 | Imprint