Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Communication and Memory Efficient Testing of Discrete Distributions
Speaker:Themis Gouleakis
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Friday, 21 June 2019
Time:15:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
This talk is about distribution testing with communication and memory constraints in the following computational models: (1) The one-pass streaming model where the goal is to minimize the sample complexity of the protocol subject to a memory constraint, and (2) A distributed model where the data samples reside at multiple machines and the goal is to minimize the communication cost of the protocol. In both these models, we provide efficient algorithms for uniformity/identity testing (goodness of fit) and closeness testing (two sample testing). Moreover, we show nearly-tight lower bounds on (1) the sample complexity of any one-pass streaming tester for uniformity, subject to the memory constraint, and (2) the communication cost of any uniformity testing protocol, in a restricted “one-pass” model of communication.
Contact
Name(s):Themistoklis Gouleakis
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Themistoklis Gouleakis, 06/19/2019 10:41 PM
  • Themistoklis Gouleakis, 06/03/2019 02:11 PM
  • Themistoklis Gouleakis, 06/03/2019 02:10 PM -- Created document.