complexity analysts

Abstract: The Holant framework provides a general setting for studying counting problems and includes graph homomorphisms (\#GH) and counting constraint satisfaction problems (\#CSP) as special cases. Over the past twenty years, a series of computational complexity dichotomies have been established for Holant problems, but the classification for complex-valued signatures is still open. The main obstacle is the case in which all signatures have even arity. In this paper, we establish a dichotomy for Holant problems with a complex-valued 4-ary signature, which is a key base case for the full classification of Holant problems. We present a new strategy by introducing Schur's theorem, the classification of finite subgroups of $\mathrm{SL}(2,\mathbb{C})$ and stable subgroup sequences into the proof. These new techniques are of independent interest.

Abstract: Proportional Approval Voting (PAV) chooses committees that maximize a sum of harmonic utilities. We study the set of maximizing committees: whether a candidate belongs to some or all of them, whether the optimum is unique, and how many optima exist. When the committee size is part of the input, the three decision problems are $Δ_2^\mathrm{P}$-complete. Uniqueness remains hard for instances with at most two optimal committees. Counting optimal committees is $\#\!\cdot\!\mathrm{OptP}$-complete under metric reductions: every function $f$ in this class reduces to an election with exactly $f(x)+1$ optimal committees. The reductions encode satisfying assignments directly as committees and use harmonic marginal rewards to realize binary objectives with polynomially many voters. Each satisfying assignment has a unique committee representation, and fixed clause ballots give these representations the same clause score. We also prove Turing equivalence with $\#\mathrm{SAT}$ and show that membership of the counting problem in $\#\mathrm{P}$ would imply $\\mathrm{NP}=\mathrm{coNP}$.

Abstract: We study the fine-grained complexity of computing approximate Nash equilibria and approximating the value of free games in the regime where the approximation error vanishes. Under the PCP for PPAD and ETH for PPAD conjectures, we show that computing $\varepsilon$-approximate Nash equilibria in 2-player $N$-action normal-form games requires time $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$, thus showing that the classical Lipton-Markakis-Mehta algorithm (2003) is optimal through all regimes of $\varepsilon = ω(1/\sqrt{N})$. While such optimality was known in the constant-$\varepsilon$ regime (Rubinstein, 2016), previous work could only rule out significantly smaller running times of $N^{O(\log(N)/\varepsilon)}$ in the regime $\varepsilon = o(1)$. Using similar techniques, we then establish an analogous tight lower bound of $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$ under ETH for $\varepsilon$-additive value estimation in free games, when $\varepsilon \geq 2^{-o(\sqrt{\log N})}$, answering a question of Aaronson, Impagliazzo, and Moshkovitz (2014).