The Theoretical Limits of Statistical High Dimensional...

Google Tech Talks September 6, 2007 ABSTRACT Suppose we have $n$ Bernoulli(1/2) long sequences of bits. Let $n-2m$ sequences be completely independent, while the remaining $2m$ sequences are composed of $m$ independent pairs. The interdependence within each pair is that their bits agree with probability $1/20$. The exponent $1/p$ is optimal in a large natural class of algorithms which we name Bucketing Codes. Moreover if one sequence out of each pair belongs to a known set of $n^{(2p-1)^{2}-\epsilon}$ sequences, than pairing can be done using order $n$ comparisons! These results are extended to a general discrete independent data model. The performance of Bucketing Codes is bounded by a newly defined...