Tata Institute of Fundamental Research
The Sensitivity Conjecture is True
STCS Student Seminar
Speaker:
Suhail Sherif
Organiser:
Anamay Tengse
Date:
Friday, 26 Jul 2019, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: Decision trees form a basic model of computation, with connections to many areas in complexity and approximation theory. The decision tree complexity D(f) of a Boolean function f is the number of bits of the input you have to query in order to determine the value of f on that input.
It is easy to see that it is hard for a decision tree to differentiate between the input being a specific string s and the input being different from s in 1 bit. Turning this into a lower bound method yields the sensitivity bound s(f). A slightly more generalized lower bound method that also follows from this is the block sensitivity bound bs(f). Hence s(f)
| Speaker: | Suhail Sherif |
| Organiser: | Anamay Tengse |
| Date: | Friday, 26 Jul 2019, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: Decision trees form a basic model of computation, with connections to many areas in complexity and approximation theory. The decision tree complexity D(f) of a Boolean function f is the number of bits of the input you have to query in order to determine the value of f on that input.
It is easy to see that it is hard for a decision tree to differentiate between the input being a specific string s and the input being different from s in 1 bit. Turning this into a lower bound method yields the sensitivity bound s(f). A slightly more generalized lower bound method that also follows from this is the block sensitivity bound bs(f). Hence s(f)
It is easy to see that it is hard for a decision tree to differentiate between the input being a specific string s and the input being different from s in 1 bit. Turning this into a lower bound method yields the sensitivity bound s(f). A slightly more generalized lower bound method that also follows from this is the block sensitivity bound bs(f). Hence s(f)