title: Hay In A Haystack Problems
tags: math
h1:

source: [This Chalk Talk video by Kelsey Houston-Edwards](https://www.youtube.com/watch?v=4weMmFZSBtI)

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