BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/268
DTSTAMP:20230914T125917Z
SUMMARY:A Little Advice can be very Helpful
DESCRIPTION:Speaker: Arkadev Chakraborty (University of Toronto\nTheory Gro
up\n27 King's College Circle\nToronto\, Ontario\nCanada M5S 1A1)\n\nAbstra
ct: \nProving superpolylogarithmic lower bounds for dynamic data structure
s has remained an open problem despite years of research. Recently\, Patra
scu proposed an exciting new approach for breaking this barrier via a two
player communication model in which one player gets private advice at the
beginning of the protocol. He gave reductions from the problem of solving
an asymmetric version of set-disjointness in his model to a diverse collec
tion of natural dynamic data structure problems in the cell probe model. H
e also conjectured that\, for any hard problem in the standard two-party c
ommunication model\, the asymmetric version of the problem is hard in his
model\, provided not too much advice is given.\n\nWe prove several surpris
ing results about his model. We show that there exist Boolean functions re
quiring linear randomized communication complexity in the two-party model\
, for which the asymmetric versions in Patrascu's model have deterministic
protocols with exponentially smaller complexity. For set-disjointness\, w
hich also requires linear randomized communication complexity in the two-p
arty model\, we give a deterministic protocol for the asymmetric version i
n his model with a quadratic improvement in complexity. These results demo
nstrate that Patrascu's conjecture\, as stated\, is false. In addition\, w
e show that the randomized and deterministic communication complexities of
problems in his model differ by no more than a logarithmic multiplicative
factor.\n\nWe also prove lower bounds in some restricted versions of this
model for natural functions such as set-disjointness and inner product. A
ll of our upper bounds conform to these restrictions (joint work with Jeff
Edmonds\, Faith Ellen and Toniann Pitassi).\n
URL:https://www.tcs.tifr.res.in/web/events/268
DTSTART;TZID=Asia/Kolkata:20120423T113000
DTEND;TZID=Asia/Kolkata:20120423T123000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR