complexity analysts

Abstract: We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs. This answers an open problem posed by Chan, Vassilevska Williams, and Xu [STOC 2022], and constitutes the first such tight real-to-integer self-reduction in fine-grained complexity. Our proof relies on a surprising combination of the Frank--Tardos theorem from optimization with Freiman-type theorems from additive combinatorics.

Abstract: Comb inequalities are important cutting planes for the symmetric travelling salesman problem, yet the complexity of their exact separation has remained a longstanding question in polyhedral combinatorics. We present a reduction from 3-SAT proving that deciding whether a comb inequality is violated is NP-complete and that the corresponding separation problem is NP-hard. This result holds even when the input vector belongs to the subtour elimination polytope, every edge value is zero, one half or one and the support graph is nonplanar with maximum degree four. The reduction constructs a graph in which six-vertex ladder gadgets encode Boolean relations and cubic graphs enforce consistency among occurrences of each logical variable. For a propositional logic formula with $v$ variables and $m$ clauses, the constructed graph has $40v+70m+30$ vertices and a linear number of positive edges. The reduction also proves hardness when every permitted tooth has two or four vertices with half of the tooth in the handle. We discuss consequences for approximating the maximum comb violation, optimization over the comb relaxation and explain why hardness of separation does not automatically transfer to larger inequality families.

Abstract: A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically stable if one cannot even encode arbitrarily long linear orders. Bonnet et al. (ICALP 2025) characterised monadic dependence by flip-separability: for every vertex weighting, boundedly many flips - complementations of the adjacency relation within a vertex subset - make every ball of radius $r$ carry at most an $\varepsilon$-fraction of the weight, so that every set carrying an $\varepsilon$-fraction has two elements pulled apart. We introduce flip-packability: boundedly many graphs, each obtained from the input by boundedly many flips and all determined by the weighting before any set is presented, such that every set carrying an $\varepsilon$-fraction of the weight has $m$ elements pairwise far apart in one of them. The number of flips producing each graph depends on the radius alone; only the number of graphs depends on $\varepsilon$ and $m$. We prove that a class of graphs is flip-packable if and only if it is monadically stable, and $2$-flip-packable, that is, flip-packable with $m=2$, if and only if it is monadically dependent. The passage from two scattered elements to $m$ is thus exactly what separates the two notions. For monadically stable classes we show that the flipped graphs can be computed from the weighting in cubic time. Varying the three parameters of the definition - the sparsifying operation, the radius, and the number $m$ of elements scattered - produces eight known characterisations of sparse and dense graph classes from the same template. In each case $m$ separates a depth-like notion from its width-like relaxation: treedepth from treewidth, shrubdepth from cliquewidth, and monadic stability from monadic dependence.

Abstract: We show an information-theoretic lower bound of $Ω\left(\frac{\log n \log m}{\log \log n + \log \log m}\right)$ for online set cover against randomized algorithms, for all sufficiently large $m$ and $n$ satisfying $\log^2 n \leq m \leq 2^n$.

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).