  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 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 the generalization of (hyper-)graph containers to Partition
Containers.
