Revision #1 Authors: Nader Bshouty, Hanna Mazzawi

Accepted on: 19th March 2012 14:42

Downloads: 2568

Keywords:

We prove that for every prime $p\le poly(n)$ there exists a $(0,1)$-matrix

$M$ of size $t_p(n,m)\times n$ where

$$t_p(n,m)=O\left(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})}\right)$$ such that every

$m$ columns of $M$ are linearly independent over $\Z_p$, the field

of integers modulo $p$ (and therefore over any field of

characteristic $p$ and over the real numbers field $\R$). In

coding theory this matrix is a parity-check $(0,1)$-matrix over

$\Z_p$ of a linear code of distance $m$. Using the Hamming bound

(for $p0$ and gives a deterministic subexponential time

algorithm (in~$n$) for constructing~$M$.

This solves the following open problems:

\noindent $\bullet$ \ {\bf Coin Weighing Problem}: Suppose that

$n$ coins are given among which there are at most $m$ counterfeit

coins of arbitrary weights. There is a non-adaptive algorithm that

finds the counterfeit coins and their weights in $t(n,m)=O((m\log

n)/\log m)$ weighings.

Previous algorithm, \cite{CK08}, solves the problem (with the same

complexity) only for weights between $n^{-a}$ and $n^b$ for

constants $a$ and $b$ and finds the counterfeit coins but not

their weights.

\noindent $\bullet$ \ {\bf Reconstructing Graph from Additive

Queries}: Suppose that $G$ is an unknown weighted graph with~$n$

vertices and $m$ edges. There exists a non-adaptive algorithm that

finds the edges of $G$ and their weights in $O(t(n,m))$ additive

queries.

Previous algorithms, \cite{CK08,BM09}, solves the problem only for

weights between $n^{-a}$ and $n^b$ for constants $a$ and $b$ and

finds the edges but not their weights.

\noindent $\bullet$ \ {\bf Signature Coding Problem}: Consider $n$

stations and at most $m$ of them want to send messages from $\Z_p$

through an adder channel, that is, a channel that its output is

the sum of the messages. Then all messages can be sent (encoded

and decoded) with $O(t(n,m))$ transmissions. Previous algorithms,

\cite{BG07}, run with the same number of transmissions only for

messages in $\{0,1\}$.

Simple information theoretic arguments show that all the above

bounds are tight.

TR09-067 Authors: Hanna Mazzawi, Nader Bshouty

Publication: 31st August 2009 16:52

Downloads: 3343

Keywords:

We prove that for every prime $p$ there exists a $(0,1)$-matrix

$M$ of size $t_p(n,m)\times n$ where

$$t_p(n,m)=O\left(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})}\right)$$ such that every

$m$ columns of $M$ are linearly independent over $\Z_p$, the field

of integers modulo $p$ (and therefore over any field of

characteristic $p$ and over the real numbers field $\R$). In

coding theory this matrix is a parity-check $(0,1)$-matrix over

$\Z_p$ of a linear code of distance $m$. Using the Hamming bound

(for $p<m$) and information theoretic argument (for $p\ge m$) it

can be shown that the above bound is tight.

To reduce the number of random bits, we extend this result to a

$(0,1)$-matrix of size $s_p(n,m,d)\times n$ where

$s_p(n,m,d)=O(t(n,m))$ and each row in the matrix is a tensor

product (Kronecker product) of a constant $d$ $(0,1)$-vectors of

size $n^{1/d}$. This reduces the number of random bits from

$O(t_p(n,m)n)$ to $O(t_p(n,m)n^{\epsilon})$ for any constant

$\epsilon>0$ and gives a deterministic subexponential time

algorithm (in~$n$) for constructing~$M$.

This solves the following open problems:

\noindent $\bullet$ \ {\bf Coin Weighing Problem}: Suppose that

$n$ coins are given among which there are at most $m$ counterfeit

coins of arbitrary weights. There is a non-adaptive algorithm that

finds the counterfeit coins and their weights in $t(n,m)=O((m\log

n)/\log m)$ weighings.

Previous algorithm, \cite{CK08}, solves the problem (with the same

complexity) only for weights between $n^{-a}$ and $n^b$ for

constants $a$ and $b$ and finds the counterfeit coins but not

their weights.

\noindent $\bullet$ \ {\bf Reconstructing Graph from Additive

Queries}: Suppose that $G$ is an unknown weighted graph with~$n$

vertices and $m$ edges. There exists a non-adaptive algorithm that

finds the edges of $G$ and their weights in $O(t(n,m))$ additive

queries.

Previous algorithms, \cite{CK08,BM09}, solves the problem only for

weights between $n^{-a}$ and $n^b$ for constants $a$ and $b$ and

finds the edges but not their weights.

\noindent $\bullet$ \ {\bf Signature Coding Problem}: Consider $n$

stations and at most $m$ of them want to send messages from $\Z_p$

through an adder channel, that is, a channel that its output is

the sum of the messages. Then all messages can be sent (encoded

and decoded) with $O(t(n,m))$ transmissions. Previous algorithms,

\cite{BG07}, run with the same number of transmissions only for

messages in $\{0,1\}$.

Simple information theoretic arguments show that all the above

bounds are tight.