Query Matrices for Retrieving Binary Vectors Based on the Hamming Distance Oracle

Understand

The Hamming oracle returns the Hamming distance between an unknown binary $n$-vector $x$ and a binary query $n$-vector y.

• The objective is to determine $x$ uniquely using a sequence of $m$ queries.
• What are the minimum number of queries required in the worst case? We consider the query ratio $m/n$ to be our figure of merit and derive upper bounds on the query ratio by explicitly constructing $(m,n)$ query matrices.
• We show that our recursive and algebraic construction results in query ratios arbitrarily close to zero.