Revision #4 Authors: Oded Goldreich, Dana Ron, Madhu Sudan

Accepted on: 27th August 1999 00:00

Downloads: 3555

Keywords:

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 Authors: Oded Goldreich, Dana Ron, Madhu Sudan

Accepted on: 18th June 1999 00:00

Downloads: 2693

Keywords:

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 Authors: Oded Goldreich, Dana Ron, Madhu Sudan

Accepted on: 8th February 1999 00:00

Downloads: 2596

Keywords:

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 Authors: Oded Goldreich, Dana Ron, Madhu Sudan

Accepted on: 22nd November 1998 00:00

Downloads: 2605

Keywords:

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

TR98-062 Authors: Oded Goldreich, Dana Ron, Madhu Sudan

Publication: 29th October 1998 09:12

Downloads: 2495

Keywords:

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