Lex Fridman · Optimal dating strategy - mathematician explains | Lex Fridman

1. 1. Worst-case analysis judges a problem by the single hardest input, ignoring all fine-grained structure of individual instances.
2. 2. Worst-case thinking is a poor guide for personal decisions like marriage, where the average case may serve better.
3. 3. The secretary problem is an online algorithm where candidates arrive one at a time and you must commit or pass without seeing the future.
4. 4. The optimal secretary strategy is to reject everyone during an initial probationary window, then accept the first candidate better than all previously seen.
5. 5. Online algorithms are designed to perform well against any input sequence because the future sequence cannot be modeled in advance.
6. 6. A major open direction is 'beyond worst case analysis': figuring out which structural features of natural problem instances an algorithm can actually exploit.
7. 7. If worst-case-derived algorithms are not good enough for applications, one alternative is to model more of the surrounding world and exploit that structure.