Sublinear Algorithms for Graph Processing
Event details
| Date | 18.07.2017 |
| Hour | 13:00 › 15:00 |
| Speaker | Aidasadat Mousavifar |
| Location | |
| Category | Conferences - Seminars |
EDIC Candidacy Exam:
Exam president: Prof. Rüdiger Urbanke
Thesis director: Prof. Michael Kapralov
Co-examiner: Prof. Ola Svensson
Abstract:
The goal of the thesis is to design efficient sublinear (time, space, communication) algorithms for fundamental graph problems. In particular, a major direction that I would like to explore is the design of sublinear time, or local, graph exploration primitives for approximating solution cost of combinatorial optimisation problems. Examples include approximating matching size, testing cluster structure of graphs using carefully designed randomised exploration processes that can be implemented in sublinear time, space or communication. Recent years have seen significant progress on several of the questions above, but many exciting directions remain largely unexplored.
Background papers:
Yoshida, Yuichi, Masaki Yamamoto, and Hiro Ito. "Improved constant-time approximation algorithms for maximum matchings and other optimization problems." SIAM Journal on Computing 41.4 (2012): 1074-1093.
Czumaj, Artur, Pan Peng, and Christian Sohler. "Testing cluster structure of graphs." Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing. ACM, 2015.
Raz, Ran. "Fast learning requires good memory: A time-space lower bound for parity learning." Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on. IEEE, 2016.
Exam president: Prof. Rüdiger Urbanke
Thesis director: Prof. Michael Kapralov
Co-examiner: Prof. Ola Svensson
Abstract:
The goal of the thesis is to design efficient sublinear (time, space, communication) algorithms for fundamental graph problems. In particular, a major direction that I would like to explore is the design of sublinear time, or local, graph exploration primitives for approximating solution cost of combinatorial optimisation problems. Examples include approximating matching size, testing cluster structure of graphs using carefully designed randomised exploration processes that can be implemented in sublinear time, space or communication. Recent years have seen significant progress on several of the questions above, but many exciting directions remain largely unexplored.
Background papers:
Yoshida, Yuichi, Masaki Yamamoto, and Hiro Ito. "Improved constant-time approximation algorithms for maximum matchings and other optimization problems." SIAM Journal on Computing 41.4 (2012): 1074-1093.
Czumaj, Artur, Pan Peng, and Christian Sohler. "Testing cluster structure of graphs." Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing. ACM, 2015.
Raz, Ran. "Fast learning requires good memory: A time-space lower bound for parity learning." Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on. IEEE, 2016.
Practical information
- General public
- Free
Contact
- EDIC - [email protected]