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 …

Property testing is concerned with the design of super-fast algorithms for the structural
analysis of large quantities of data. The aim is to unveil global features of the data, such as …

The spectrum of a network or graph G=(V,E) with adjacency matrix A, consists of the
eigenvalues of the normalized Laplacian L=ID^-1/2AD^-1/2. This set of eigenvalues …

We give a nearly optimal sublinear-time algorithm for approximating the size of a minimum
vertex cover in a graph G. The algorithm may query the degree deg (v) of any vertex v of its …

Consider Sym (n) endowed with the normalized Hamming metric dn. A finitely generated
group Γ is P-stable if every almost homomorphism ρ nk: Γ→ Sym (nk)(ie, for every g, h∈ Γ …

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 …

The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete
graphs. Recently, a class of (even-hole, K 4)-free graphs was constructed, that still has …

Graph kernels are applied heavily for the classification of structured data. However, their
expressivity is assessed almost exclusively from experimental studies and there is no …

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 …

We study the problem of recognizing the cluster structure of a graph in the framework of
property testing in the bounded degree model. Given a parameter ε, a d-bounded degree …