| Line 1: |
Line 1: |
| − | == Title ==
| |
| − | Parallel Algorithms for Geometric Graph Problems
| |
| | | | |
| − | == Speaker ==
| |
| − | [http://grigory.us Grigory Yaroslavtsev]
| |
| − |
| |
| − | == Abstract ==
| |
| − | I will describe algorithms for geometric graph problems in the modern parallel models inspired by MapReduce. The talk will be self-contained, including a formal introduction of the modern theoretical computational models used to capture computations in massively parallel “MapReduce”-like systems. It will also include a sample of major open problems in the area.
| |
| − |
| |
| − | For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes an approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms).
| |
| − |
| |
| − | I will also show how the main ideas from the MST algorithm can be captured within a general “Solve-and-Sketch” algorithmic framework that we develop. Besides MST it also applies to the approximate Earth-Mover Distance (EMD) and the transportation cost problem. Algorithms designed in the “Solve-and-Sketch” framework have implications which go beyond parallel models. In particular, our work implies new near-linear time algorithms for EMD cost and transportation cost in the plane. Other implications include algorithms in the streaming with sorting model.
| |
| − |
| |
| − | Joint work with Alexandr Andoni, Krzysztof Onak and Aleksandar Nikolov.
| |
| − |
| |
| − | == Bio ==
| |
| − | Grigory Yaroslavtsev is a postdoctoral fellow at the Warren Center for Network and Data Sciences. He was previously a Postdoctoral Fellow in Mathematics at Brown University, ICERM. He received his Ph.D. in Theoretical Computer Science in 2013 from Pennsylvania State University and an M.Sc. in Applied Mathematics and Physics from the Academic University of the Russian Academy of Sciences in 2010.
| |
| − |
| |
| − | Grigory works on efficient algorithms for sparsification, summarization and testing properties of large data, including approximation, parallel and online algorithms, learning theory and property testing, communication and information complexity and private data release.
| |
