Shyan Akmal

Shyan Akmal, Nick Fischer

Weighted variants of triangle detection are an important object of study because of their prominence in fine-grained complexity. We revisit the Node-Weighted Triangle problem, where the goal is to decide if a vertex-weighted graph contains a triangle whose node weights sum to zero. This problem has been the focus of a celebrated line of work, beginning with a subcubic-time algorithm [Vassilevska, Williams; STOC '06], and culminating in algorithms running almost in matrix multiplication time, $O(\textsf{MM}(n) + n^2\cdot 2^{O(\sqrt{\log n})})$ [Czumaj, Lingas; SODA '07], [Vassilevska W., Williams; STOC '09]. This runtime is almost-optimal, since even detecting an unweighted triangle is conjectured to require matrix multiplication time $\textsf{MM}(n)$. However, the superpolylogarithmic $2^{Ω(\sqrt{\log n})}$ overhead persists in a world where near-optimal matrix multiplication is possible (i.e., $\textsf{MM}(n) \leq n^2\text{poly}(\log n)$). In this paper, we present a new algorithm solving Node-Weighted Triangle in $O(\textsf{MM}(n))$ time, closing the gap to unweighted triangle detection completely. Remarkably, our algorithm is much simpler than previous approaches, which use involved recursion schemes and communication protocols.

Shyan Akmal, Ryan Williams

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 $ρ\in (0,1)$ with bounded denominator, we give an algorithm that can determine whether a given $k$-CNF has at least $ρ\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$.