BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/718
DTSTAMP:20230914T125935Z
SUMMARY:Rényi Information Complexity and an Information Theoretic Characte
rization of the Partition Bound
DESCRIPTION:Speaker: Manoj M. Prabhakaran (Indian Institute of Technology\n
Department of Computer Science\nand Engineering\nPowai\nMumbai 400076)\n\n
Abstract: \nWe introduce a new information-theoretic complexity measure IC
∞ for 2-party functions which is a lower-bound on communication complexi
ty\, and has the two leading lower-bounds on communication complexity as i
ts natural relaxations: (external) information complexity (IC) and logarit
hm of partition complexity (prt). These two lower-bounds had so far appear
ed conceptually quite different from each other\, but we show that they ar
e both obtained from IC∞ using two different\, but natural relaxations:\
n\nThe relaxation of IC∞ that yields IC is to change the order of Rényi
mutual information used in its definition from ∞ to 1.\n\n\nThe relaxat
ion of IC∞ that yields log prt is to replace protocol transcripts used i
n the definition of IC∞ with what we term "pseudotranscripts\," which om
its the interactive nature of a protocol\, but only requires that the prob
ability of any transcript given inputs x and y to the two parties\, factor
izes into two terms which depend on x and y separately.\n\n\nWe also show
that if both the above relaxations are simultaneously applied to IC∞\, w
e obtain a complexity measure that is lower-bounded by the (log of) relaxe
d partition complexity\, a complexity measure introduced by Kerenidis et a
l. (FOCS 2012). We obtain a similar (but incomparable) connection betwee
n (external) information complexity and relaxed partition complexity as Ke
renidis et al.\, using an arguably more direct proof (this is joint work w
ith Vinod Prabhakaran).\n
URL:https://www.tcs.tifr.res.in/web/events/718
DTSTART;TZID=Asia/Kolkata:20161018T160000
DTEND;TZID=Asia/Kolkata:20161018T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR