BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Memory and communication lower bounds
DTSTART:20210623T100000
DTEND:20210623T120000
DTSTAMP:20260501T134029Z
UID:c2bd5894a16bdab2f50d22a83ee33191cab2afe2e990a0003cd244ba
CATEGORIES:Conferences - Seminars
DESCRIPTION:Mikhail Makarov\nEDIC candidacy exam\nexam president: Prof. Ol
 a Svensson\nthesis advisor: Prof. Michael Kapralov\nco-examiner: Prof. Mik
 a Göös\n\nAbstract\nAs distributed computing and learning becomes more p
 opular\, the interest arises in minimizing the required memory\, communica
 tion and number of samples needed to do computational tasks. Our research 
 goal is to provide lower bounds on these parameters in a range of differen
 t setups. In this proposal we discuss three existing works and their relat
 ion to our research. We examine the memory-sample lower bounds for learnin
 g discrete tasks and communication lower bounds for checking the graph con
 nectivity in distributed computing.\n\nBackground papers\n- Yu\,H. (2021).
  Tight Distributed Sketching Lower Bound for Connectivity: https://www.cs.
 princeton.edu/~hy2/files/conn_skt.pdf\n- Steinhard\, J.\, Valiant\, G.\, &
  Wager\, S. (2016\, June). Memory\, communication\, and statistical querie
 s: http://proceedings.mlr.press/v49/steinhardt16.pdf\n- Garg\, S.\, & Raz\
 , R. (2019\, January). Time-space lower bounds for two-pass learning: http
 s://drops.dagstuhl.de/opus/volltexte/2019/10844/pdf/LIPIcs-CCC-2019-22.pdf
 \n 
LOCATION:
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR