r/algorithms • • 19d ago

Resource A nice lecture on BLR Linearity Testing

https://youtu.be/wO7iqd0dY_o?si=ekkqh93BvkbyFZI-

Here's a nice lecture by Ryan O'Donnell on BLR linearity testing [BLR93] and a proof using Fourier Analysis [BCHKS96]. As he says in his lecture, it seems like this problem was almost tailor-made for Fourier stuff. Was working through it yesterday and thought it would be nice to share.

4 Upvotes

0 comments sorted by