אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

I will explain a phenomenon that I call the "Average Scale is Boring Principle" (you may help me come up with a better name): The 01010101... sequence, for example, has high variance on a local scale, but if you look at larger scales each segment looks identical. For another example, the sequence 0^n1^n looks different at a global scale, but on almost all short intervals it is constant. I will formalize a sense in which some sequences have high variance on some scales, but for *all* sequences the average scale is "boring". (Bonus: the proof is only a few lines!)

Interestingly, the same principle recently came in handy in two very different projects: one on approximation algorithms for Edit Distance and Longest Common Subsequence, and the other on online algorithms for calibrated forecasting.

The talk is based on things I learnt from Xiao Mao and Binghui Peng.