Memory and communication lower bounds


Event details

Date and time 23.06.2021 10:0012:00  
Speaker Mikhail Makarov
Category Conferences - Seminars
EDIC candidacy exam
exam president: Prof. Ola Svensson
thesis advisor: Prof. Michael Kapralov
co-examiner: Prof. Mika Göös

As distributed computing and learning becomes more popular, the interest arises in minimizing the required memory, communication and number of samples needed to do computational tasks. Our research goal is to provide lower bounds on these parameters in a range of different setups. In this proposal we discuss three existing works and their relation to our research. We examine the memory-sample lower bounds for learning discrete tasks and communication lower bounds for checking the graph connectivity in distributed computing.

Background papers
- Yu,H. (2021). Tight Distributed Sketching Lower Bound for Connectivity:
- Steinhard, J., Valiant, G., & Wager, S. (2016, June). Memory, communication, and statistical queries:
- Garg, S., & Raz, R. (2019, January). Time-space lower bounds for two-pass learning:

Practical information

  • General public
  • Free


  • EDIC


EDIC candidacy exam