  Majority-SAT is the problem of determining whether an input $n$-variable
formula in conjunctive normal form (CNF) has at least $2^{n-1}$ satisfying
assignments. Majority-SAT and related problems have been studied extensively in
various AI communities interested in the complexity of probabilistic planning
and inference. Although Majority-SAT has been known to be PP-complete for over
40 years, the complexity of a natural variant has remained open:
Majority-$k$SAT, where the input CNF formula is restricted to have clause width
at most $k$.
  We prove that for every $k$, Majority-$k$SAT is in P. In fact, for any
positive integer $k$ and rational $\rho \in (0,1)$ with bounded denominator, we
give an algorithm that can determine whether a given $k$-CNF has at least $\rho
\cdot 2^n$ satisfying assignments, in deterministic linear time (whereas the
previous best-known algorithm ran in exponential time). Our algorithms have
interesting positive implications for counting complexity and the complexity of
inference, significantly reducing the known complexities of related problems
such as E-MAJ-$k$SAT and MAJ-MAJ-$k$SAT. At the heart of our approach is an
efficient method for solving threshold counting problems by extracting
sunflowers found in the corresponding set system of a $k$-CNF.
  We also show that the tractability of Majority-$k$SAT is somewhat fragile.
For the closely related GtMajority-SAT problem (where we ask whether a given
formula has greater than $2^{n-1}$ satisfying assignments) which is known to be
PP-complete, we show that GtMajority-$k$SAT is in P for $k\le 3$, but becomes
NP-complete for $k\geq 4$. These results are counterintuitive, because the
``natural'' classifications of these problems would have been PP-completeness,
and because there is a stark difference in the complexity of GtMajority-$k$SAT
and Majority-$k$SAT for all $k\ge 4$.
