BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/780
DTSTAMP:20230914T125938Z
SUMMARY:On Query and Communication Complexity
DESCRIPTION:Speaker: Sagnik Mukhopadhyay\n\nAbstract: \nIn the first part\
, we will consider the connection between two well-known complexity measur
es --- communication complexity and query complexity. For a composed funct
ion $f \\circ g$\, where $f: \\{0\,1\\}^p \\rightarrow \\mathcal{Z}$ and $
g : \\{0\,1\\}^n \\times \\{0\,1\\}^n \\rightarrow \\{0\,1\\}$\, we will s
how a sufficient condition for $g$ such that the communication complexity
of $f \\circ g$ becomes tightly bounded by the query complexity of $f$ tim
es the communication complexity of $g$. Such a theorem is known as simulat
ion theorem or lifting theorem in literature. We will also show two well-k
nown functions for which the said condition holds. This part deals with de
terministic complexity measures.\n\nIn the second part of the talk\, we wi
ll deal with randomized complexity measure. We consider a specific compose
d function $\\text{elim} \\circ g$\, namely the elimination function\, and
we will demonstrate a key property of $g$\, namely the regularity propert
y\, which is closely related to the communication complexity of the elimin
ation problem. To this end\, we will show a tight connection between regul
arity and another well-studied pseudo-random property of $g$\, namely\, di
screpancy.\n\nIn the third part\, we will get into the realm of asymmetric
communication complexity where one of the players holds an input of consi
derably smaller length than that of the other player. We will show two res
ults here --- (a) We will consider function like $g^p$ and show direct-sum
results for such functions in asymmetric setting\, and (b) we will show t
ight randomized lower bound for a composed function\, namely\, the asymmet
ric unordered search function. We will allude to the role of regularity in
obtaining such a lower bound.\n\nIn the last part of the talk\, we will t
alk about communication complexity in multiparty number-in-hand coordinato
r model. We will show a tight lower bound for a well-studied function (in
two-party model)\, namely the tribes function\, in this setting.\n
URL:https://www.tcs.tifr.res.in/web/events/780
DTSTART;TZID=Asia/Kolkata:20170601T103000
DTEND;TZID=Asia/Kolkata:20170601T113000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR