Algorithm design for the 21^st century

シュワルツマン研究室　SCHWARTZMAN Laboratory
准教授：シュワルツマン グレゴリー（SCHWARTZMAN, Gregory）

E-mail：
［研究分野］
Algorithms, Distributed Systems, Theoretical Computer Science
［キーワード］
Distributed Systems, Graph Algorithms, Combinatorial Optimizations, Streaming Algorithms

研究を始めるのに必要な知識・能力

I’m looking for highly motivated students with an interest in math and puzzle solving. You should have completed a basic algorithms and data structure course, and should have some familiarity with graphs.

この研究で身につく能力

You will learn how to find, define and solve algorithmic problems. To achieve this, you will learn the basics of graph theory and algorithm design. You will learn how to read and understand the scientific literature. You will learn how to tackle a hard algorithmic problem from start to finish. And finally, you will learn how to communicate your results effectively.

【就職先企業・職種】 Academia, IT industry

研究内容

Many real-world challenges, from analyzing huge social networks to efficient communication in distributed networks, can be expressed in the language of graph theory. Starting from the 70s and up until today, the field of graph algorithm design has proven itself as an invaluable tool in tackling many fundamental, real world algorithmic challenges. To achieve this, many “classical” graph algorithms were introduced.

With the recent emergence of Blockchain, autonomous cars and big data, there has been a shift in how algorithms are designed. In the “classical” model the data was small enough to be held in memory, there was a single processor and the data could be freely accessed throughout the computation. But this does not capture the challenges of big data and distributed computing, where data is too big to fit into memory, or is distributed among a huge network of servers. This requires us to design new graph algorithmic tools to handle these new and exciting challenges. Below are two examples of such algorithmic models.

Streaming model:

In the streaming model we wish to perform some computation over data which is too large too store in memory. For example, imagine our input is Facebook’s social graph, where nodes are users and edges are friend relations. While the nodes can easily fit into RAM, the edges might require several terabytes of memory. To overcome this, we process the edges in a stream. That is, the algorithm sees all edges in the graph one by one, but has limited memory. The algorithm performs some computation while edges arrive and finally outputs the results of the computation. The memory restriction is quite challenging and requires new algorithmic tools and techniques.

Distributed model:

In the distributed model we have some network of independent processors that wish to achieve some common goal in a decentralized manner. This model captures problems such as packet routing over the internet, achieving consensus in a blockchain network or a fleet of autonomous vehicles trying to optimize congestion. Here the main bottleneck is the communication between processors in the network. The crux here is that computation happens simultaneously throughout the network, which gives rise to new problems, such as symmetry breaking. The goal here is to design communication efficient algorithms for the task at hand.
The above are just two examples, while many more fascinating models exist (online algorithms, property testing, dynamic data structures). Our goal is to explore these new models of computation and try to accurately represent the algorithmic challenges of the 21^st century. We aim to define new models, and design efficient algorithms for fundamental problems.

主な研究業績

1. Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman: A Distributed (2+ε)-Approximation for Vertex Cover in O(logΔ / ε log logΔ) Rounds. PODC 2016
2. Ami Paz, Gregory Schwartzman: A (2 + ε)-Approximation for Maximum Weight Matching in the Semi-Streaming Model. SODA 2017
3. Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, Yadu Vasudev: Fast Distributed Algorithms for Testing Graph Properties. DISC 2016