Theory Underlying Algorithms

Co-located with SODA'20, January 5-8, 2020, at Hilton Salt Lake City Center, Utah

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ω/2n^ω/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^ω/2) time with high probability.

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² 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/ε)^O(1) many complete bipartite graphs (whose joint refinement gives the partition), which in some cases can be of more use than just the partition.

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

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

Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise lp low rank approximation. Our results give improved algorithms for these applications.

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ý.