BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/519
DTSTAMP:20230914T125927Z
SUMMARY:On the Structure of Boolean Functions With Small Spectral Norm
DESCRIPTION:Speaker: Swagato  Sanyal\n\nAbstract: \nAbstract: Let f: F_2^n 
 -> {+1\, -1} be a Boolean function with the first Fourier norm A and Fouri
 er sparsity s. We will prove that there is an affine subspace of the vecto
 r space F_2^n\, of dimension O(A)\, on which the f is constant. If time pe
 rmits\, we will prove that f has a parity decision tree of depth O(\\sqrt{
 s}).  These results are by Tsang et al which improves on earlier results 
 by Shpilka et al.\n\nReferences:\n\nAmir Shpilka\, Avishay Tal\, Ben lee V
 olk. On the Structure of Boolean Functions with Small Spectral Norm. ITCS 
 2014\n\nHing Yin Tsang\, Chung Hoi Wong\, Ning Xie\, Shengyu Zhang. Fourie
 r sparsity\, spectral norm and the log rank conjecture. FOCS 2013\n
URL:https://www.tcs.tifr.res.in/web/events/519
DTSTART;TZID=Asia/Kolkata:20140718T143000
DTEND;TZID=Asia/Kolkata:20140718T160000
LOCATION:D-405
END:VEVENT
END:VCALENDAR