The Theoretical Limits of Statistical High Dimensional...

Back


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

Channel: Howto & Style
Uploaded: October 9, 2007 at 4:06 am
Author: googletechtalks

Length: 00:55:26
Rating: 4.00
Views: 618

Tags: google howto theoretical limits statistical

Video Comments:
No Comments