BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Marius Zimand (Towson University) DTSTART:20231206T160000Z DTEND:20231206T171500Z DTSTAMP:20260423T040000Z UID:AAIT/26 DESCRIPTION:Title: Lo ssless expanders and Information Reconciliation with no shared randomness. \nby Marius Zimand (Towson University) as part of Seminar on Algorithm ic Aspects of Information Theory\n\n\nAbstract\nLossless expanders are bip artite graphs in which for every sufficiently small set on the left side o f the bipartition\, most of the outgoing edges lead to distinct vertices. I will present an application of such graphs in Information Reconciliation . This is a protocol with 2 parties: Sender and Receiver. Sender has a str ing x and Receiver has a string y. For instance\, think that x is an updat ed version of y. Sender sends a message m which allows Receiver to constru ct x. The goal is to minimize the length of m\, taking into account the co rrelation of x and y. This correlation can be formalized in different ways and is only known by Receiver. Standard solutions require Sender and Rece iver to share randomness. In my talk\, I will explain how lossless expande rs are used to obtain Information Reconciliation with no shared randomness .\n\nThe main idea is from the paper B. Bauwens and M. Zimand\, Universal almost optimal compression and Slepian-Wolf coding in probabilistic polyno mial time\, Journal of the ACM\, April 2023 (also available at arXiv:1911. 04268)\, but I'll focus on just one particular aspect.\n LOCATION:https://researchseminars.org/talk/AAIT/26/ END:VEVENT END:VCALENDAR