Tata Institute of Fundamental Research
Polynomial time local decision
STCS Student Seminar
Speaker:
Soumyadeep Paul (TIFR)
Organiser:
Shanthanu Suresh Rai
Date:
Thursday, 12 Dec 2024, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Distributed local decision studies the power of distributed algorithms. Typically, the processors are assumed to have unbounded power for local computation, focussing only on the communication between the parties. In this talk, I will be introducing the LOCAL model of distributed computing and local decision and some complexity classes related to them. We will then look at some complexity classes which take into account local computation as well and their connections to centralized complexity classes.
This talk is based on this paper: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.27
| Speaker: | Soumyadeep Paul (TIFR) |
| Organiser: | Shanthanu Suresh Rai |
| Date: | Thursday, 12 Dec 2024, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Distributed local decision studies the power of distributed algorithms. Typically, the processors are assumed to have unbounded power for local computation, focussing only on the communication between the parties. In this talk, I will be introducing the LOCAL model of distributed computing and local decision and some complexity classes related to them. We will then look at some complexity classes which take into account local computation as well and their connections to centralized complexity classes.
This talk is based on this paper: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.27