  We present connections between the recent literature on multigroup fairness
for prediction algorithms and classical results in computational complexity.
Multiaccurate predictors are correct in expectation on each member of an
arbitrary collection of pre-specified sets. Multicalibrated predictors satisfy
a stronger condition: they are calibrated on each set in the collection.
Multiaccuracy is equivalent to a regularity notion for functions defined by
Trevisan, Tulsiani, and Vadhan (2009). They showed that, given a class $F$ of
(possibly simple) functions, an arbitrarily complex function $g$ can be
approximated by a low-complexity function $h$ that makes a small number of
oracle calls to members of $F$, where the notion of approximation requires that
$h$ cannot be distinguished from $g$ by members of $F$. This
complexity-theoretic Regularity Lemma is known to have implications in
different areas, including in complexity theory, additive number theory,
information theory, graph theory, and cryptography. Starting from the stronger
notion of multicalibration, we obtain stronger and more general versions of a
number of applications of the Regularity Lemma, including the Hardcore Lemma,
the Dense Model Theorem, and the equivalence of conditional pseudo-min-entropy
and unpredictability. For example, we show that every boolean function
(regardless of its hardness) has a small collection of disjoint hardcore sets,
where the sizes of those hardcore sets are related to how balanced the function
is on corresponding pieces of an efficient partition of the domain.
