BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1355
DTSTAMP:20231109T095402Z
SUMMARY:Fourier Growth of Communication Protocols for XOR Functions
DESCRIPTION:Speaker: Makrand Sinha (University of Illinois Urbana-Champaign
)\n\nAbstract: \nThe Fourier growth of a function refers to the growth of
the sum of absolute values of the level-k Fourier coeﬀicients. Bounds on
the Fourier growth\, even for the first few levels\, have important appli
cations in pseudorandomness and quantum-versus-classical separations. Tigh
t bounds on the Fourier growth have been studied for many classes of funct
ions\, including decision trees and parity decision trees.\n \nWe study t
he Fourier growth of functions associated to communication protocols for X
OR functions (functions evaluated on the point-wise XOR of Alice's and Bob
's inputs). If a protocol C computes an XOR function\, then C(x\,y) is a f
unction of x + y. This motivates us to study the XOR-fiber of the communic
ation protocol C\, defined as h(z) := E[C(x\,y)|x + y = z]. These function
s form a powerful class which includes decision trees and parity decision
trees. Proving tight bounds on the Fourier growth of XOR fibers also has a
pplications to the Gap-Hamming problem and improved quantum versus classic
al separations in communication complexity.\n \nIn this talk\, we present
improved Fourier growth bounds for the XOR-fibers of randomized protocols
that communicate d bits. For the first level\, we show a tight O(sqrt{d})
bound. For the second level\, we show an improved O(d^{3/2}) bound. We co
njecture that the optimal bound is O(d.polylog(n)) and leave this as an op
en question.\n \nOur proof relies on viewing the protocol and its Fourier
spectrum as a martingale. One crucial ingredient we use to control the st
ep sizes is a spectral notion of k-wise independence. Loosely speaking\, t
his corresponds to sets such that the k-th moments of the uniform distribu
tion on the set are well-behaved in all directions. We show how imposing s
pectral k-wise independence on Alice's and Bob's sets allows us to prove b
ounds on the level-k Fourier growth of XOR-fibers. We also provide a way o
f adaptively partitioning a large set into a few spectrally k-wise indepen
dent sets.\n \nJoint work with Uma Girish (Princeton University)\, Avisha
y Tal (UC Berkeley) and Kewen Wu (UC Berkeley).\n
URL:https://www.tcs.tifr.res.in/web/events/1355
DTSTART;TZID=Asia/Kolkata:20231122T143000
DTEND;TZID=Asia/Kolkata:20231122T153000
LOCATION:A-269 (DAA Seminar)
END:VEVENT
END:VCALENDAR