The Theoretical Limits of Statistical High Dimensional...

Channel:

Google TechTalks

Subscribers:

348,000

Published on October 9, 2007 3:03:36 AM ● Video Link: https://www.youtube.com/watch?v=4J9dXvuV1jQ

Duration: 55:27

1,571 views

3

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...