Departmental colloquium 11.1.23
Dr. Or Zamir
Institute for Advanced Study and Princeton University
Will lecture on
Algorithmic Applications of Hypergraph and Partition Containers
We present a general method to convert algorithms into faster algorithms for almost-regular input instances. Informally, an almost-regular input is an input in which the maximum degree is larger than the average degree by at most a constant factor. This family of inputs vastly generalizes several families of inputs for which we commonly have improved algorithms, including bounded-degree inputs and random inputs. It also generalizes families of inputs for which we don't usually have faster algorithms, including regular-inputs of arbitrarily high degree and all very dense inputs. We apply our method to achieve breakthroughs in exact algorithms for several central NP-Complete problems including k-SAT, Graph Coloring, and Maximum Independent Set.
Our main tool is the first algorithmic application of the relatively new Hypergraph Container Method (Saxton and Thomason 2015, Balogh, Morris and Samotij 2015). This recent breakthrough, which generalizes an earlier version for graphs (Kleitman and Winston 1982, Sapozhenko 2001), has been used extensively in recent years in extremal combinatorics. An important component of our work is a new generalization of (hyper-)graph containers to Partition Containers.
:Short bio
Or Zamir is an associate research scholar at Princeton University and a member of the Institute for Advanced Study. Prior to that, he completed his PhD at Tel Aviv University.
Or has a broad interest in applications of combinatorics and graph theory to theoretical computer science.
He received several fellowships and awards including the Rothschild fellowship, the Blavatnik Prize, the Deutsch Prize, and Best Student Paper at ICALP 2021.