Hay In A Haystack Problems

source: This Chalk Talk video by Kelsey Houston-Edwards

Hay In A Haystack Problem: actually finding something that's almost everywhere.

Examples

1. Friends and Strangers Theorem
   • Is it possible to invite n people without creating a red or blue k-person clique for other numbers n and k
   • There is a probabalistic method prove that shows that such cliques always exist, for some n and k
   • Actually finding such a clique, even if we know it exists, is a hard problem.
2. Normal numbers
   • Every n-digit subsequence occurs with equal probability, for all n.
   • Almost all numbers are normal.
   • Very few examples of normal numbers are known, except for examples specifically constructed to be normal.
3. (ref: Avi Wigderson, who credits Howard Karloff).
   • Error Correcting Codes
     • Good error correcting codes are abundant, but hard to find. Shannon proved that they exist, but it took decades to find explicit examples.
   • Compressed Sensing