BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230320T120000Z
UID:2cd5e752ab7c7c9989f8850afb981edd-433
DTSTAMP:19700101T120016Z
DESCRIPTION:Criticality of AC0-formulae
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/433/criticality-of-ac0-formulae/
SUMMARY:Hastads celebrated switching lemma gives inverse-exponential bounds (In terms of t) on the probability that an k-DNF when hit by a p-restriction requires decision-trees of depth larger than t. The switching lemma has proved to be extremely powerful, since its discovery, leading to optimal size lower bounds for AC0-circuits [Hastad 1986] and AC0 formulae [Rossman 2015] against the parity function.
<br>
More recently, the search for optimal correlation bounds against parity led to the notion of criticality [Rossman 2019]. The criticality of a Boolean function 
f:{0,1}n → {0,1} is the minimum λ≥1 such that for all positive integers t, we have 
Prρ∼Rp[DTdepth(f|ρ)≥t]≤(pλ)t.
<br>
Hastad (2014) proved that size S and depth (d+1) AC0-circuits have criticiality at most O((logS)d) leading to optimal correlation bounds of AC0-circuits against parity. Rossman (2019) subsequently proved that size S and depth (d+1) AC0-formulae, which are regular (i.e., all gates of same depth have fan-in) having criticality at most O((logS/d)d).
<br>
In this work, we strengthen and unify all the above results by proving that any (not necessarily regular) AC0-formula of size S and depth (d+1) have criticality at most O((logS/d)d). The criticality bound implies tight correlation bounds against parity, tight Fourier concentration results and improved #SAT algorithm for AC0-formulae. 
<br>
The talk is based on joint works with Tulasimohan Molli and Ashutosh Shankar.
<br>
Microsoft teams link:
<br>
Teams link 
<br>
https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
<br>
<br>
We are grateful to the Kirani family for generously supporting the theory seminar series
<br>
<br>
Hosts: Rameesh Paul, Aditya Subramanian, Aditya Abhay Lonkar and Rahul Madhavan
DTSTART:20230320T120000Z
END:VEVENT
END:VCALENDAR