  A set of high dimensional points $X=\{x_1, x_2,\ldots, x_n\} \subset R^d$ in
isotropic position is said to be $\delta$-anti concentrated if for every
direction $v$, the fraction of points in $X$ satisfying $|\langle x_i,v \rangle
|\leq \delta$ is at most $O(\delta)$. Motivated by applications to
list-decodable learning and clustering, recent works have considered the
problem of constructing efficient certificates of anti-concentration in the
average case, when the set of points $X$ corresponds to samples from a Gaussian
distribution. Their certificates played a crucial role in several subsequent
works in algorithmic robust statistics on list-decodable learning and settling
the robust learnability of arbitrary Gaussian mixtures, yet remain limited to
rotationally invariant distributions.
  This work presents a new (and arguably the most natural) formulation for
anti-concentration. Using this formulation, we give quasi-polynomial time
verifiable sum-of-squares certificates of anti-concentration that hold for a
wide class of non-Gaussian distributions including anti-concentrated bounded
product distributions and uniform distributions over $L_p$ balls (and their
affine transformations). Consequently, our method upgrades and extends results
in algorithmic robust statistics e.g., list-decodable learning and clustering,
to such distributions. Our approach constructs a canonical integer program for
anti-concentration and analysis a sum-of-squares relaxation of it, independent
of the intended application. We rely on duality and analyze a
pseudo-expectation on large subsets of the input points that take a small value
in some direction. Our analysis uses the method of polynomial reweightings to
reduce the problem to analyzing only analytically dense or sparse directions.
