Tata Institute of Fundamental Research
Criticality of boolean functions and Entropy Switching lemma for DNFs
STCS Student Seminar
Speaker:
Tulasi mohan Molli
Organiser:
Prerona Chatterjee
Date:
Friday, 20 Aug 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
A p-random restriction is a random partial input obtained by independently leaving each input variable unset with probability p setting them to either 0,1 with (1-p)/2 each.
Criticality of a boolean function f is the inverse of the probability p at which the decision tree depth t of a random restriction of f goes down exponentially in t.The ground breaking work of Hastad’s Switching lemma is a bound on criticality of CNFs and DNFs. Rossman defined the notion of criticality and showed its connection to average case lower bounds, fourier tail bounds, and decision tree size.
In this talk we will see implications of bounds on criticality to average case lower bounds, Fourier tail bounds and decision tree size and an Entropy Switching lemma for DNFs due to Rossman.
Zoom link:
https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
| Speaker: | Tulasi mohan Molli |
| Organiser: | Prerona Chatterjee |
| Date: | Friday, 20 Aug 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
A p-random restriction is a random partial input obtained by independently leaving each input variable unset with probability p setting them to either 0,1 with (1-p)/2 each.
Criticality of a boolean function f is the inverse of the probability p at which the decision tree depth t of a random restriction of f goes down exponentially in t.The ground breaking work of Hastad’s Switching lemma is a bound on criticality of CNFs and DNFs. Rossman defined the notion of criticality and showed its connection to average case lower bounds, fourier tail bounds, and decision tree size.
In this talk we will see implications of bounds on criticality to average case lower bounds, Fourier tail bounds and decision tree size and an Entropy Switching lemma for DNFs due to Rossman.
Zoom link:
https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
Criticality of a boolean function f is the inverse of the probability p at which the decision tree depth t of a random restriction of f goes down exponentially in t.The ground breaking work of Hastad’s Switching lemma is a bound on criticality of CNFs and DNFs. Rossman defined the notion of criticality and showed its connection to average case lower bounds, fourier tail bounds, and decision tree size.
In this talk we will see implications of bounds on criticality to average case lower bounds, Fourier tail bounds and decision tree size and an Entropy Switching lemma for DNFs due to Rossman.
Zoom link:
https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09