BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/403
DTSTAMP:20230914T125923Z
SUMMARY:Public vs Private-Coin Information Complexity
DESCRIPTION:Speaker: Mr. Ankit Garg (Princeton University\nDepartment of Co
 mputer Science\n35\, Olden Street\nPrinceton\, NJ 08544\nUnited States of 
 America\n )\n\nAbstract: \nWe study the relation between public and priva
 te-coin information complexity. Improving a recent result by Brody et al.\
 , we prove that a one-round private-coin protocol with information cost ca
 n be simulated by a one-round public-coin protocol with information cost $
 \\le I + \\log(I) + O(1)$. This question is connected to the question of c
 ompression of interactive protocols and direct sum for communication compl
 exity.\nWe also give a lower bound. We exhibit a one-round private-coin pr
 otocol with information cost $\\tilda$ $n/2 - \\log(n)$ which cannot be si
 mulated by any public-coin protocol with information cost $n/2 - O(1)$. Th
 is example also explains an additive $\\log$ factor incurred in the study 
 of communication complexity of correlations by Harsha et al.\n
URL:https://www.tcs.tifr.res.in/web/events/403
DTSTART;TZID=Asia/Kolkata:20130910T143000
DTEND;TZID=Asia/Kolkata:20130910T153000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR