Campus Event Calendar
Event Entry
What and Who
Parallel Repetition in Communication (and Information)
Pachara Sawettamalya
Other:
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 10 April 2025
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Parallel repetition concerns solving multiple independent instances, say n, of the same problem. Naively, this can be achieved by executing each instance individually; thus using n times the amount of resource for computing a single instance. One might ask the converse: does solving n instances require \Omega(n) times the amount of resource of solving a single instance. In this talk, we will survey the regime where the "resource" is communication and see how tools from information theory can help partially resolve such questions. As time permits, we will discuss its application in proving dynamic streaming lower bounds for computing a spanning forest.
Contact
Nidhi Rathi
+49 681 9325 1134
--email hidden
Virtual Meeting Details
Zoom
897 027 2575
passcode not visible
logged in users only
Nidhi Rathi, 04/08/2025 15:52
Nidhi Rathi, 03/17/2025 17:22
Nidhi Rathi, 03/17/2025 17:17 -- Created document.
Nidhi Rathi, 03/17/2025 17:22
Nidhi Rathi, 03/17/2025 17:17 -- Created document.