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.
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.
His fields of interest include algorithms, data structures, graph theory, and combinatorics.
Or received several fellowships and awards including the Rothschild fellowship, the Blavatnik Prize, the Deutsch Prize, and Best Student Paper at ICALP 2021.
His work was covered in several tech and academic magazines including IEEE Spectrum, The Register, NSF Math Institutes, New Scientist and TechTalks.