Memory and communication lower bounds
Event details
| Date | 23.06.2021 |
| Hour | 10:00 › 12: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
Abstract
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: https://www.cs.princeton.edu/~hy2/files/conn_skt.pdf
- Steinhard, J., Valiant, G., & Wager, S. (2016, June). Memory, communication, and statistical queries: http://proceedings.mlr.press/v49/steinhardt16.pdf
- Garg, S., & Raz, R. (2019, January). Time-space lower bounds for two-pass learning: https://drops.dagstuhl.de/opus/volltexte/2019/10844/pdf/LIPIcs-CCC-2019-22.pdf
exam president: Prof. Ola Svensson
thesis advisor: Prof. Michael Kapralov
co-examiner: Prof. Mika Göös
Abstract
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: https://www.cs.princeton.edu/~hy2/files/conn_skt.pdf
- Steinhard, J., Valiant, G., & Wager, S. (2016, June). Memory, communication, and statistical queries: http://proceedings.mlr.press/v49/steinhardt16.pdf
- Garg, S., & Raz, R. (2019, January). Time-space lower bounds for two-pass learning: https://drops.dagstuhl.de/opus/volltexte/2019/10844/pdf/LIPIcs-CCC-2019-22.pdf
Practical information
- General public
- Free
Organizer
- EDIC