Event
CCSP/ISR Seminar: Vinay Vaishampayan, Query Matrices for the Hamming Oracle
Thursday, March 8, 2012
2:00 p.m.-3:30 p.m.
2168 A V Williams
Prakash Narayan
301 405 3661
prakash@umd.edu
Communication, Control and Signal Processing/ISR Seminar
Thursday, March 8, 2012, Professor Prakash Narayan welcomes Dr. Vinay Vaishampayan (AT&T Labs-Research) as part of a joint CCSP/ISR Seminar. Dr. Vaishampayan will give a talk titled Query Matrices for the Hamming Oracle.
Abstract
x is an unknown binary string of length n. In response to an n-bit query y, the Hamming oracle returns the Hamming distance d(x,y). The problem is to construct a set of queries that allow us to determine x based on the query results. All queries must be set up in advance, i.e. queries are not allowed to depend on the response of the oracle to preceding queries. Our figure of merit is the query ratio, i.e. the ratio of the number of queries to the length of the string.
Connections to the distinct-subset-sum problem and to other more widely known problems will be explored. Bounds on the achievable query ratio as a function of the string length n will be derived.
An algebraic construction will be presented along with a decoding algorithm, and it will be shown that query ratios arbitrarily close to zero can be achieved.
Biography
Vinay Vaishampayan is Distinguished Member of Technical Staff at AT&T Labs-Research, Shannon Laboratory, located in Florham Park, NJ. Prior to joining AT&T in 1996, he was Associate Professor of Electrical Engineering, Texas A&M University. His background is in communications, signal processing and coding. At AT&T he has been involved in a broad range of research work---recent areas are optical networking, mobile systems, statistical modeling of user behavior. His main long-term interest is in the interplay of coding and geometry and its application to information science.
