BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Alexander Kozachinskiy (Catholic University of Chile)
DTSTART:20240410T150000Z
DTEND:20240410T161500Z
DTSTAMP:20260423T052925Z
UID:AAIT/32
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/AAIT/32/">In
 formation-theoretic methods in communication complexity.</a>\nby Alexander
  Kozachinskiy (Catholic University of Chile) as part of Seminar on Algorit
 hmic Aspects of Information Theory\n\n\nAbstract\nImagine that Alice and B
 ob both hold a binary string of length n\, and they want to know if there 
 is a position\, where both their strings have 1. This problem is called Di
 sjointness. A fundamental result in communication complexity states that e
 ven if Alice and Bob have access to randomness and are allowed to error wi
 th small probability\, they need to send each other Omega(n) bits to solve
  Disjointness. \n\nIn the talk\, I will present an information complexity 
 proof technique that was developed by different authors in the 2000s and b
 y now has become classical. This method\, in the nutshell\, uses the chain
  rule for mutual information to formalize an intuition that we cannot do b
 etter in solving Disjointness than checking individually all n positions.\
 n
LOCATION:https://researchseminars.org/talk/AAIT/32/
END:VEVENT
END:VCALENDAR