BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Communication Complexity of $\\mathsf{XOR}$ Functions
DTSTART;VALUE=DATE-TIME:20180417T103000Z
DTEND;VALUE=DATE-TIME:20180417T120000Z
DTSTAMP;VALUE=DATE-TIME:20180423T173714Z
UID:indico-event-6362@cern.ch
DESCRIPTION:Given a boolean function $f : \\{0\, 1\\}^n \\rightarrow \\{0\
, 1\\}$ define the function $f \\circ \\mathsf{XOR}$ on $2n$ bits by $f \\
circ \\mathsf{XOR} (x_1\, \\dots\, x_n\, y_1\, \\dots\, y_n) = f(x_1 \\opl
us y_1\, \\dots\, x_n \\oplus y_n)$. Such a function is called an $\\math
sf{XOR}$ function. A natural communication game for such a function is as
follows. Alice is given $x = (x_1\, \\dots\, x_n)$\, Bob is given $y = (
y_1\, \\dots\, y_n)$\, and they jointly wish to compute $f \\circ \\mathsf
{XOR}(x\, y)$. They have unbounded computational power individually and w
ish to minimize the amount of communication between them on the worst case
input.\n\nWe study the communication complexity of $\\mathsf{XOR}$ functi
ons under various randomized models\, and resolve several open questions i
n the areas of communication complexity\, boolean circuit complexity and a
nalysis of boolean functions.\n\n1) We characterize the weakly-unbounded e
rror communication complexity of $\\mathsf{XOR}$ functions in terms on a c
ertain approximation theoretic property of the outer function. We use thi
s characterization to reprove several known results. Along the way\, we al
so resolve some open questions in the area of analysis of boolean function
s.\n\n2) We prove a strong unbounded error communication complexity lower
bound for an easily describable function. We then use this to show a bool
ean circuit complexity class separation that has been open since the early
90's\, and first explicitly posed in 2005. This also resolves a recent o
pen problem in communication complexity by separating two communication co
mplexity classes.\nWe also prove lower bounds against the class of functio
ns efficiently computable by decision lists of linear threshold functions\
, and prove unbounded error communication complexity lower bounds for $\\m
athsf{XOR}$ functions when the outer function is symmetric.\n\n3) Finally\
, we separate two randomized communication complexity classes in the "numb
er on forehead" model of multiparty communication. This also implies bool
ean circuit class separations.\n\nhttps://indico.tifr.res.in/indico/confer
enceDisplay.py?confId=6362
LOCATION: A-201 (STCS Seminar Room)
URL:https://indico.tifr.res.in/indico/conferenceDisplay.py?confId=6362
END:VEVENT
END:VCALENDAR