Main Profile

At A Glance

The Theoretical Limits of Statistical High Dimensional...

Google Tech TalksSeptember 6, 2007ABSTRACTSuppose 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...
Length: 55:26

Contact

Questions about The Theoretical Limits of Statistical High Dimensional...

Want more info about The Theoretical Limits of Statistical High Dimensional...? Get free advice from education experts and Noodle community members.

  • Answer

Ask a New Question