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.

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.