Seminars

View all Seminars  |  Download ICal for this event

Fourier Growth for Communication Protocols for XOR functions

Series: Bangalore Theory Seminars

Speaker: Uma Girish,Princeton

Date/Time: Jun 25 11:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract:
Fourier growth of a Boolean function refers to the growth of the sum of absolute values of the level-k Fourier coe�?icients. Upper bounds on the Fourier growth, even for the first few levels, have important applications in pseudorandomness, learning theory, circuit lower bounds and quantum-versus-classical separations. We study the Fourier growth of functions associated with communication protocols, namely XOR functions. In this setting, Alice gets a bitstring x and Bob gets a bitstring y, and together they wish to compute a Boolean function that only depends on x+y (the point-wise Alices and Bobs inputs). If a protocol C computes an XOR function, then the output C(x,y) of the protocol is a function of x + y. This motivates us to study the XOR-fiber H of a communication protocol C defined by $H(z) := E[ C(x,y) mid x + y = z]$.
<br>
<br>
Microsoft teams link:
<br>
<a href="Link
<br>
<br>
We are grateful to the Kirani family for generously supporting the theory seminar series
<br>
<br>
Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar