Degree vs Approximate Degree for Boolean Functions



Friday, 27 November 2020, 17:15 to 18:15


The field of researching Boolean functions can be summed up as

Boolean functions: *exist*
Researchers: find out EVERYTHING

This has led to it being a very happening field with many elegant results and fascinating stories. The algebraic properties of degree and approximate degree have played prominent roles in many of these. A couple of years before I was born, Gotsman and Linial showed a purely combinatorial reformulation of the `degree vs sensitivity' question.
Last year Hao Huang shocked the world by proving this combinatorial statement with a linear algebraic argument that fits in a tweet.

Come this year and the team of Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao and Avishay Tal have delved into this linear algebraic argument and proved many other implications of it, the one most interesting to me being

approx-degree(f) ≥ Ω(√degree(f))

It is a quite elementary proof taking advantage of intuitive linear algebraic manipulations. This is what I intend to present in this student seminar.

Zoom Link: