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

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

2012-02-13

arxiv.org/abs/1202.2794v1

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Query Matrices for Retrieving Binary Vectors Based on the Hamming Distance Oracle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Query Matrices for Retrieving Binary Vectors Based on the Hamming Distance Oracle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query Matrices for Retrieving Binary Vectors Based on the Hamming Distance Oracle will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-684099