Tata Institute of Fundamental Research
Degree vs Approximate Degree for Boolean Functions
STCS Student Seminar
Speaker:
Suhail Sherif
Organiser:
Prabhat Kumar Jha
Date:
Friday, 27 Nov 2020, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
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
| Speaker: | Suhail Sherif |
| Organiser: | Prabhat Kumar Jha |
| Date: | Friday, 27 Nov 2020, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
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
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