Recently, it became apparent that a large number of the most interesting structures and
phenomena of the world can be described by networks. To develop a mathematical theory of …

We introduce a new tool for approximation and testing algorithms called partitioning oracles.
We develop methods for constructing them for any class of bounded-degree graphs with an …

A property testing algorithm for a property Π in the bounded degree graph model [7] is an
algorithm that, given access to the adjacency list representation of a graph G=(V, E) with …

Owing to their interesting spectral properties, the synthetic crystals over lattices other than
regular Euclidean lattices, such as hyperbolic and fractal ones, have attracted renewed …

In this article we survey the emerging field of descriptive graph combinatorics. This area has
developed in the last two decades or so at the interface of descriptive set theory and graph …

This book introduces important results and techniques in property testing, where the goal is
to design algorithms that decide whether their input satisfies a predetermined property in …

Motivated by the problem of testing planarity and related properties, we study the problem of
designing efficient partition oracles. A partition oracle is a procedure that, given access to …

Hyperfiniteness or amenability of measurable equivalence relations and group actions has
been studied for almost fifty years. Recently, unexpected applications of hyperfiniteness …

In the last 20 years network science has become an independent scientific field. We argue
that by building network models network scientists are able to tame the vagueness of …

Parameter testing algorithms are using constant number of queries to estimate the value of a
certain parameter of a very large finite graph. It is well‐known that graph parameters such as …