Time:
Organisers:
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:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09