Let *G* be an intersection graph of *n* geometric objects in the plane. We show
that a maximum matching in *G* can be found in *O(ρ ^{3ω/2}n^{ω/2})* time with high
probability, where

*ρ*is the density of the geometric objects and

*ω>2*is a constant such that n×n matrices can be multiplied in

*O(n*time. The same result holds for any subgraph of

^{ω})*G*, as long as a geometric representation is at hand. For this, we combine algebraic methods, namely computing the rank of a matrix via Gaussian elimination, with the fact that geometric intersection graphs have small separators. We also show that in many interesting cases, the maximum matching problem in a general geometric intersection graph can be reduced to the case of bounded density. In particular, a maximum matching in the intersection graph of any family of translates of a convex object in the plane can be found in

*O(n*time with high probability.

^{ω/2})Joint work with Édouard Bonnet and Wolfgang Mulzer.

In this talk we will discuss the relationship between property
testing in general planar graphs and the study of short random walks and
short random exploration algorithm in planar graphs. We will show that
random constant-depth, constant-breadth exploration in arbitrary planar
graphs can be used to efficiently (in a constant number of queries) test
*H*-freeness in arbitrary planar graphs, for any graph *H*. (Earlier
techniques were only able to test graph properties for planar graphs of
bounded degrees.)

This is based on joint work with Sohler, Onak, and Monemizadeh.

Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions. In this talk, I present a recent joint work with Kaave Hosseini and Shachar Lovett in which we show the strongest possible separation by constructing a Boolean matrix whose sign-rank is only 3, and yet its discrepancy is exponentially small.

The matroid matching (or matroid parity) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of independence oracle calls. Nevertheless, Lovasz (1980) showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem. More recently, a polynomial-time algorithm was developed for the weighted version. The algorithm builds on a polynomial matrix formulation using Pfaffian. This talk provides an overview of the matroid matching problem, putting emphasis on its connection to Pfaffian.

Regularity lemmas are very useful tools in graph theory and
theoretical computer science. In this talk, I'll discuss a recent
deterministic algorithm that finds, in *(1/ε) ^{O(1)}n^{2}* time, an
epsilon-regular Frieze-Kannan partition of a graph on n vertices. The
algorithm outputs an approximation of a given graph as a weighted sum of

*(1/ε)*many complete bipartite graphs (whose joint refinement gives the partition), which in some cases can be of more use than just the partition.

^{O(1)}Low-distortion metric embeddings constitute an important tool in algorithm design and have found applications in numerous data analytic tasks. A significant amount of research effort has been focused on obtaining efficient algorithms for computing an embedding of a given finite metric space into a desired host space with minimum distortion. A limitation of this type of mappings is that they are not robust with respect to noise in the form of outlier points. That is, there are examples of metric spaces that admit an embedding into some constant-dimensional normed space with constant distortion, yet by adding one more point the resulting space does not admit an embedding with better than polynomial distortion. In order to alleviate this phenomenon, we seek to design algorithms that remove some small set of outlier points, and compute an embedding of the remaining points with approximately minimum distortion. We present some recent results of this type for embedding into Euclidean space with minimum additive and multiplicative distortion.

Based on joint works with Karine Chubarian, Dingkang Wang, and Yusu Wang.

In this talk I will highlight the application of spectral graph sparsification in speeding-up the classical Newton's method, resulting the first-scalable parallel algorithm for sampling Gaussian Markov Random Fields with H-Precision matrices.

Oblivious subspace embeddings have proven to be an essential ingredient for approximately solving
numerical linear algebra problems, such as regression and low-rank approximation.
While for *p = 2* there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity,
for the important case of *p = 1*, much less was known. In this talk I will present our results on
l1 oblivious subspace embeddings, including

- nearly optimal lower bounds and
- new constructions for sparse l1 oblivious subspace embeddings.

Based on joint work with Ruosong Wang.

Grohe's theorem characterizes graph classes *C* such that CSP instances built
on *C* are exactly solvable in polynomial time. But CSPs admit good
approximation schemes beyond that, as in planar graphs. A very rough
intuition is that graphs should either have sufficiently good sublinear
separators which allow to approximate them with small pieces, or contain
expanders that allow to encode hard instances. However, the actual boundary
is very unclear, raising many questions connecting sparse graph theory with
property testing (in particular hyperfiniteness) and graph limits (in
particular regularity partitions, as used for approximation schemes in
dense graphs).

Based on joint work with Miguel Romero and Stanislav Živný.