Massive graphs, which contain millions and even billions of nodes, modeling the Internet, the World Wide Web, semantic networks and social networks, are being analyzed and processed constantly. As a result, classical models of computation, in which polynomial-time algorithms are considered efficient, may become inadequate. In the field of sublinear-time algorithms, the goal is to design extremely fast algorithms that probe only a minuscule portion of the input. Likewise, if the size of the output grows linearly in the size of the input, then it becomes desirable to provide access to parts of the output without having to store and compute it entirely. This is where Local Computation Algorithms (or the CentLocal model), as defined by Rubinfeld et al., comes into play.

In this talk I will focus on CentLocal algorithms for computational graph problems. I will start with a comparison of the CentLocal model with other models of computation which are “local” such as: (1) distributed local computation, (2) property testing, and (3) sublinear approximation algorithms. Each of these models has some limitations on the way it accesses the input, and the way it produces the output. I then will elaborate on studied connections of these models to the CentLocal model. I will overview on some of the techniques which are frequently used for designing CentLocal algorithms followed by an overview of the current state-of-the-art algorithms for various graphs problems in terms of the already established tools. At the end of the talk I will present Local Graph Generators. These oracles provide a (sublinear) probe access to a graph drawn from a certain distribution of random graphs. I will outline an implementation of such an oracle that gives access to a graph which is drawn from the Barabási-Albert Preferential Attachment model, and the random recursive tree model.

This talk is based on a recently published survey paper by Reut Levi and myself.

Shortest Path, Max Flow, and Min Cut are classical combinatorial optimization problems that have been studied extensively for decades, and many combinatorial algorithms have been developed to solve them. However, they can also be considered as convex optimization problems and, thus, can be attacked by continuous methods as well, such as gradient descent and interior point method. Recently, these techniques were combined with combinatorial structures such as sparsifiers, spanners, low-stretch trees, and congestion approximators to obtain efficient algorithms in centralized and distributed models of computation. We formulate Shortest Path and Max Flow in undirected graphs as norm-minimization problems w.r.t. the 1-norm and the infinity-norm, respectively. We exploit duality and an analytical approximation of the infinity-norm to deal with non-smoothness and obtain near-optimal distributed algorithms.

When communication goes wireless, the “network” isn’t necessarily a graph. It could be formulated as a form of a geometric hypergraph, since transmission success depends on the set of other active nodes. Such formulations are necessarily unwieldy, both for the design and analysis of algorithms, whether distributed or centralized. Instead, one could hope for a graph abstraction that captures the interference conflicts conservatively while paying a small price in performance. We outline recent progress along these lines and its implications.

The wide gap between deterministic and randomized algorithms underlies one of the central and well-known questions in Distributed Graph Algorithms. For many of the classic local problems—e.g., MIS or coloring—, while we know very simple O(log n) round randomized algorithms, obtaining a polylog n round deterministic algorithm remains a long-standing open question, since Linial's 1986 paper. This question has gained even more significance recently, due to the findings that show that to obtain faster randomized algorithms, we inevitably need to find faster deterministic algorithms.

In this talk, I will survey some of the recent developments on this topic, in three parts:

1. I will start with a complexity-theoretic characterization of this gap, which led to some surprising completeness-type results. One of these completeness results can be interpreted as showing that rounding continuous variables to integer variables, while approximately preserving some linear constraints, is all that remains to be solved deterministically.
2. In the second part, I explain how we have been able to attack this rounding question algorithmically in some special cases, leading to (improved) efficient deterministic algorithms for maximal matching and (2Δ−1)-edge coloring, the latter solving a central open problem from the 1990s, as well as a few other problems.
3. In the last part, I overview some recent (and unpublished) results, which enable us to solve a much wider range of problems deterministically, including stronger cases of the rounding problem. This part can be viewed as a general and simple-to-state recipe for derandomizing local distributed algorithms.

I will survey the recent advances in lower bound techniques for the LOCAL model. I will focus on two approaches that have proven to be powerful: “algorithmic” simulation lower bounds and the lifting of lower bounds from weaker models.

Simulation techniques have provided both strong and simple distributed computing lower bounds in the recent years. Göös et al. (PODC 2014) used a series of simulation arguments to lift a linear-in-Δ lower bound for maximal fractional matching to the standard LOCAL model. Brandt et al. (STOC 2016) used a simulation to show that a randomized algorithm for the sinkless orientation problem implies a weaker and faster algorithm, proving a lower bound of Ω(log log n) rounds. Chang et al. (FOCS 2016) gave a number of different simulation results, showing for example that algorithms with certain complexities can be automatically sped up and that randomized lower bounds imply even stronger deterministic lower bounds. I will try to illustrate the core intuition of some of these proofs and give a taste of the techniques used.

I will also talk about how some these results are starting to form a complexity theory of distributed graph algorithms, at least for the case of relatively sparse graphs. I want to highlight some of the major open questions, the shortcomings of our current proof techniques, and also some possible ways forward.

Distance labeling schemes can be viewed as an abstract framework for formulating algorithms and distributed data structures to answer distance queries on node pairs in a graph. In this talk, we will overview 15 years of progress in the area, with a focus on recent developments for the case when the desired outcome is an exact (rather than approximate) distance computation or an exact shortest path computation. We will try to shed some light on why the complexity of the distance labeling problem still remains wide open for some of the most basic graph classes, such as sparse graphs and planar graphs. More broadly, we will try to provide some insights into the principle sources of hardness of designing distributed graph oracles for the considered type of query.