  Given a randomized experiment with binary outcomes, exact confidence
intervals for the average causal effect of the treatment can be computed
through a series of permutation tests. This approach requires minimal
assumptions and is valid for all sample sizes, as it does not rely on
large-sample approximations such as the central limit theorem. We show that
these confidence intervals can be found in $O(n \log n)$ permutation tests in
the case of balanced designs, where the treatment and control groups have equal
sizes, and $O(n^2)$ permutation tests in the general case. Prior to this work,
the most efficient known constructions required $O(n^2)$ such tests in the
balanced case [Li and Ding, 2016], and $O(n^4)$ tests in the general case
[Rigdon and Hudgens, 2015]. Our results thus facilitate exact inference as a
viable option for randomized experiments far larger than those accessible by
previous methods.
