AMG is a one-day workshop that focuses on algorithms for big data and large graphs. The program consists of four invited talks, which are aimed at the general DISC audience.
AMG 2024 will be held on Friday, 1st November 2024, and will be co-located with DISC 2024. It will be possible to attend the workshop either as an online conference via Zoom or as a physical event in Madrid, Spain.
Schedule
Follow this page for updates in the programme.
All times in Central European Summer Time (CEST) GMT+2.
| AMG programme | ||
|---|---|---|
| 14:00 - 15:00 | talk 1 | Artur Czumaj: Understanding the Structure of Massive Graphs through the Lens of Property Testing |
| 15:00 - 15:50 | talk 2 | Shreyas Pai: Massively Parallel Algorithms for Relaxations of MIS |
| 15:50 - 16:20 | Coffee break | |
| 16:20 - 17:10 | talk 3 | Christian Konrad: Streaming, Communication Complexity, Matchings and MIS |
| 17:10 - 18:00 | talk 4 | Talya Eden: Techniques for Counting and Sampling Subgraphs in Sublinear-Time |
| 18:00 | Workshop ends | |
Confirmed Speakers
![[Artur Czumaj]](./files/ACz_0.jpg "Artur Czumaj")
University of Warwick
Artur Czumaj is a Professor of Computer Science and Director of the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick. He received his PhD and Habilitation degree from the University of Paderborn in Germany. His main research interest is in the design of randomized algorithms and their probabilistic analysis, with applications to property testing and sublinear algorithms, optimization algorithms, parallel and distributed computing, string matching, and algorithmic game theory.
Title: Understanding the Structure of Massive Graphs through the Lens of Property Testing
Abstract: In this talk, we will provide a soft introduction to one important approach used to study the structure of large graphs: the area of graph property testing. Then, we will survey some recent advances in this area and will discuss the impact of the area of graph property testing on recent advances in the design of graph algorithms in various settings.
![[Shreyas Pai]](./files/shreyas.jpg "Shreyas Pai")
IIT Madras
Shreyas Pai is an Assistant Professor in the Department of Computer Science and Engineering at Indian Institute of Technology Madras in Chennai. He received his PhD in Computer Science at The University of Iowa under the supervision of Prof. Sriram V. Pemmaraju in May 2021. Afterwards he was a post-doctoral fellow at Aalto University hosted by Prof. Jara Uitto till March 2024 (supported by HIIT starting August 2023). His research interests are primarily in Theory of Distributed and Parallel Computing, more specifically in Distributed Graph Algorithms and Algorithms for Large Data. He is also more generally interested in topics in Theoretical Computer Science like Communication Complexity and Combinatorial Optimization.
Title: Massively Parallel Algorithms for Relaxations of MIS
Abstract:
There has been impressive progress on designing fast algorithms for Maximal Independent Set (MIS) in the massively parallel computation (MPC) model. However, we still don’t know whether these runtime guarantees are truly optimal. In this talk we will look at two relaxations of the MIS problem that allow us to achieve an optimal running time in the MPC model.
First, we will look at the 2-ruling set problem, where we relax the maximality condition. The second is constant approximation for correlation clustering where we relax the independence condition. For both these problems we can design algorithms that run in constant time in the linear memory MPC model. These algorithms more versatile in the sense that they can be implemented in other models that process massive graphs, such as the semi-streaming model.
![[Christian Konrad]](./files/me-2-blur.jpg "Christian Konrad")
University of Bristol
Christian Konrad is a Senior Lecturer (equivalent to Associate Professor in the North American system) at the University of Bristol, UK. Before joining Bristol, he held postdoctoral positions at the University of Warwick and the University of Reykjavik. He earned his PhD from the University of Paris Diderot and holds a Master's degree in Computer Science with Mathematics from the Technical University of Munich.
Christian's research primarily focuses on algorithms in resource-constrained models, with a particular emphasis on data streaming algorithms. His broader interests extend to query complexity, distributed computing, online algorithms, and communication complexity.
Title: Streaming, Communication Complexity, Matchings and MIS
Abstract:
This talk explores the connections between Streaming Algorithms and Communication Complexity, using the Maximum Matching and the Maximal Independent Set (MIS) problems as key examples.
Streaming algorithms for graph problems process sequences of edge insertions and deletions that make up a graph while using a memory that is much smaller than the graph itself. Communication Complexity examines the number of bits that multiple parties must exchange to solve a given problem. These two fields are closely linked, as lower bounds in communication complexity imply lower bounds on the space requirements of streaming algorithms. In this talk, we will explore this connection through the lens of the Maximum Matching and MIS problems, tracing how this relationship has been leveraged from the earliest works to the present.
![[Talya Eden]](./files/Talya Eden-001.jpg "Talya Eden")
Bar Ilan University
Talya Eden is an Assistant Professor at the computer science department at Bar Ilan University. She works on sublinear-time and randomized graph algorithms for huge data sets. Her work focuses on theoretical and applied graph parameter estimation in sublinear-time, as well as graph algorithms in other related areas, such as the streaming model, the massively parallel computation model, and learning-augmented algorithms.
Talya completed her PhD at the School of Electrical Engineering at Tel Aviv University under the supervision of Prof. Dana Ron, and then continued on to a postdoctoral fellowship with the Foundations of Data Science Institute at MIT and the Computer Science department at Boston University, where she was hosted by Prof. Ronitt Rubinfeld, Prof. Pioter Indyk, and Prof. Sofya Raskhodnikova. Talya has won several awards for her work, including the EATCS Distinguished Dissertation Award in Theoretical Computer Science, a Rothschild Postdoctoral Fellowship, a Schmidt Postdoctoral Award, a Ben Gurion University postdoctoral fellowship, a Weinstein Graduate Studies Prize, and the Azrieli Fellows Scholarship.
Title: Techniques for Counting and Sampling Subgraphs in Sublinear-Time
Abstract:
Over the last ten years, several methods have been proposed for estimating and sampling subgraphs without fully traversing the entire graph. This talk aims to highlight key randomization techniques that underpin these methods. These tools, though simple enough to be explained in a few slides, are powerful enough to achieve optimal results in estimating and sampling edges and cliques. The goal is for the audience to get a sufficient understanding of the details, in order to be able to reproduce the results themselves.
Based on joint works with Dana Ron, C. Seshadhri, Will Rosenbaum, Jakub Tetek, Shyam Narayanan, Saleet Mossel, Ronitt Rubinfeld, Shankha Biswas.