Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Algorithms for Online Calibration, Edit Distance, and LCS via the "Average Scale is Boring Principle"
event speaker icon
Aviad Rubinstein (Stanford University)
event date icon
Thursday, 01.01.2026, 12:30
event location icon
Taub 401

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.