BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/685
DTSTAMP:20230914T125934Z
SUMMARY:Complexity Measures of Boolean Functions
DESCRIPTION:Speaker: Swagato Sanyal\n\nAbstract: \nBoolean functions are c
entral to computer science. This presentation will focus on Boolean functi
ons from the perspective of certain measures of complexity.\n\nIn the firs
t part of the presentation\, our focus will be two Fourier analytic comple
xity measures of Boolean functions: Fourier sparsity and Fourier dimension
. We will present a near-optimal upper bound of Fourier dimension of Boole
an functions in terms of Fourier sparsity.\n\nThe second part will concent
rate on different query complexity measures of Boolean functions: determin
istic\, randomized zero-error and randomized bounded-error\, and relations
hips amongst them. We will see explicit constructions of functions for whi
ch these measures are polynomially separated\, and more widely than was kn
own before our work.\n\nWe present a lower bound on the PTF-sparsity of th
e Inner product mod 2 function that is better than the previously known bo
und by a factor of 5/2.\n\nFinally\, we present an optimal hypercontractiv
e inequality for Fourier-sparse real-valued functions on the Boolean hyper
cube.\n \n
URL:https://www.tcs.tifr.res.in/web/events/685
DTSTART;TZID=Asia/Kolkata:20160520T103000
DTEND;TZID=Asia/Kolkata:20160520T113000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR