Query Matrices for Retrieving Binary Vectors Based on the Hamming Distance Oracle
This addresses a theoretical retrieval problem in information theory, with incremental improvements in query efficiency.
The paper tackles the problem of uniquely determining an unknown binary vector using Hamming distance queries, deriving upper bounds on the query ratio and showing it can be made arbitrarily close to zero through recursive and algebraic constructions based on constant-weight codes.
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. Our construction is based on codes of constant weight. A decoding algorithm for recovering the unknown binary vector is also described.