Arithmetic circuit complexity studies the complexity of computing polynomials using only arithmetic operations such as addition, multiplication, subtraction, and division. Polynomials over rings of integers model counting problems. Similarly, polynomials over semirings such as tropical semirings model optimization problems. Circuits over semirings then model so called pure algorithms, algorithms that only use the operations in the semiring. In this paper, we do a complexity-theoretic study of the power and limitations of circuits (which represent dynamic programs) over semirings: - We define VNP over min-plus semirings, which can faithfully represent problems such as computing min-weight perfect matchings and min-weight Hamiltonian cycles where we have efficiently verifiable certificates. Unlike over rings, we complement the values in the certificate for free as complementation is impossible over min-plus semirings. We prove a dichotomy theorem that states that if we only complement logarithmically many values, this class is same as VP over min-plus semirings. If we complement super-logarithmically many values, then VNP ≠ VP. - We consider constant-width ABPs (which are also called incremental dynamic programs that are restricted to use only a constant number of registers) and show that even simple problems like computing the min-weight 2-edge-matching is impossible with width 2 (or 2 registers). However, with width 3 (or 3 registers), such programs can compute everything. More generally, we show that constant-depth formulas are efficiently simulated by constant-width ABPs. - We show that an exponential hypercube sum (min in the semiring) over even provably weak models such as width-2 ABPs and products of linear forms are the same as VNP.

We study the Boolean Satisfiability problem (SAT) in the framework of diversity, where one asks for multiple solutions that are mutually far apart (i.e., sufficiently dissimilar from each other) for a suitable notion of distance/dissimilarity between solutions. Interpreting assignments as bit vectors, we take their Hamming distance to quantify dissimilarity, and we focus on the problem of finding two solutions. Specifically, we define the problem Max Differ SAT (resp. Exact Differ SAT) as follows: Given a Boolean formula ϕ on n variables, decide whether ϕ has two satisfying assignments that differ on at least (resp. exactly) d variables. We study the classical and parameterized (in parameters d and n-d) complexities of Max Differ SAT and Exact Differ SAT, when restricted to some classes of formulas on which SAT is known to be polynomial-time solvable. In particular, we consider affine formulas, Krom formulas (i.e., 2-CNF formulas) and hitting formulas. For affine formulas, we show the following: Both problems are polynomial-time solvable when each equation has at most two variables. Exact Differ SAT is NP-hard, even when each equation has at most three variables and each variable appears in at most four equations. Also, Max Differ SAT is NP-hard, even when each equation has at most four variables. Both problems are 𝖶[1]-hard in the parameter n-d. In contrast, when parameterized by d, Exact Differ SAT is 𝖶[1]-hard, but Max Differ SAT admits a single-exponential FPT algorithm and a polynomial-kernel. For Krom formulas, we show the following: Both problems are polynomial-time solvable when each variable appears in at most two clauses. Also, both problems are 𝖶[1]-hard in the parameter d (and therefore, it turns out, also NP-hard), even on monotone inputs (i.e., formulas with no negative literals). Finally, for hitting formulas, we show that both problems can be solved in polynomial-time.

For any fixed positive integer r and a given budget k, the r-Eigenvalue Vertex Deletion (r-EVD) problem asks if a graph G admits a subset S of at most k vertices such that the adjacency matrix of G⧵S has at most r distinct eigenvalues. The edge deletion, edge addition, and edge editing variants are defined analogously. For r = 1, r-EVD is equivalent to the Vertex Cover problem. For r = 2, it turns out that r-EVD amounts to removing a subset S of at most k vertices so that G⧵ S is a cluster graph where all connected components have the same size. We show that r-EVD is NP-complete even on bipartite graphs with maximum degree four for every fixed r > 2, and FPT when parameterized by the solution size and the maximum degree of the graph. We also establish several results for the special case when r = 2. For the vertex deletion variant, we show that 2-EVD is NP-complete even on triangle-free and 3d-regular graphs for any d ≥ 2, and also NP-complete on d-regular graphs for any d ≥ 8. The edge deletion, addition, and editing variants are all NP-complete for r = 2. The edge deletion problem admits a polynomial time algorithm if the input is a cluster graph, while - in contrast - the edge addition variant is hard even when the input is a cluster graph. We show that the edge addition variant has a quadratic kernel. The edge deletion and vertex deletion variants admit a single-exponential FPT algorithm when parameterized by the solution size alone. Our main contribution is to develop the complexity landscape for the problem of modifying a graph with the aim of reducing the number of distinct eigenvalues in the spectrum of its adjacency matrix. It turns out that this captures, apart from Vertex Cover, also a natural variation of the problem of modifying to a cluster graph as a special case, which we believe may be of independent interest.