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