Jayalal Sarma

Balagopal Komarath, Harshil Mittal, Jayalal Sarma

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: i) We define $\mathsf{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 $\mathsf{VP}$ over min-plus semirings. If we complement super-logarithmically many values, then $\mathsf{VNP} \neq \mathsf{VP}$. ii) 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. iii) 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 $\mathsf{VNP}$.

Nagashri Krishnakumar, Harshil Mittal, Jayalal Sarma

The labelled reachability problem for undirected graphs with edges labelled by elements of a monoid $M$ (more generally, groupoids or magmas) captures the classes $\sf{L}$ and $\sf{NL}$. Given a graph $G(V, E)$ labelled by $ϕ~\colon E \to M$, $s,t \in V$ and an accepting subset $F \subseteq M$, the problem asks to test whether there is a walk $P$ from $s$ to $t$ in $G$ where $ϕ(P) \in F$. Ramaswamy et al. (2019) studied the variant where the accepting element is part of the input for aperiodic monoids and groups. Motivated by the success in designing space-bounded algorithms for the undirected graph reachability problem, we study the labelled reachability problem when the accepting set is also fixed. This reveals finer complexity bounds and dichotomies for the problem based on the monoid and the accepting set. Previous results imply that the problem is in $\sf{L}$ for any finite accepting subset when $M$ is a group or belongs to $\sf{DA}$. We prove the following (for finite monoids): 1) For any monoid $M$, the problem is in $\sf{L}$ when the accepting element is the identity of $M$. If the accepting element is an idempotent, under suitable constraints, the problem is $\sf{NL}$-hard. 2) For any commutative monoid $M$, the problem is in $\sf{L}$ for all $F \subseteq M$. 3) For any $\mathcal{L}(\mathcal{R})$-commutative union-of-groups (UoG) monoid $M$, the problem is in $\sf{L}$ for all $F\subseteq M$. We show deterministic logspace algorithms for UoG monoids that are neither $\mathcal{L}$-commutative nor $\mathcal{R}$-commutative, under certain constraints. 4) For the monoids $\sf{BA_2}$ and $\sf{U}$, we show a dichotomy: for all $F \subseteq M$, the problem is either $\sf{NL}$-complete or in $\sf{L}$. Our results exploit the connection between Green's relations in the UoG monoids and the properties of the product graph (a graph introduced by Ramaswamy et al. (2019)).

Sutanay Bhattacharjee, Ameya Panse, Jayalal Sarma

Color refinement is an important technique that works very well in practice for the graph isomorphism problem. Tinhofer graphs are the class of graphs for which refinement together with individualization correctly tests graph isomorphism against every other graph, irrespective of the choices of vertices made during individualization. Motivated by the fact that Tinhofer graphs form a natural boundary for efficient graph isomorphism tests based on color refinement, in this paper, we introduce a hierarchy of graph classes within the class of Tinhofer graphs. We call a graph $G$ $k$-Tinhofer if, after $k$ rounds of individualization and refinement, the resulting colored graphs remain isomorphic for every graph $H \cong G$, irrespective of the choices of vertices made during individualization. Arvind et al. (2017) studied a hierarchy of graph classes motivated by color refinement - discrete, amenable, Tinhofer, and refinable graphs. We show that the $k$-Tinhofer hierarchy lies between the class of all graphs and Tinhofer graphs, with refinable graphs coinciding with the first level of the hierarchy. We obtain two characterizations of $k$-Tinhofer graphs: an algebraic characterization in terms of orbit partitions induced by pointwise stabilizers of automorphism groups, and a combinatorial characterization in terms of individualization-refinement trees and quotient graphs. For every fixed integer $k \ge 0$, there exist vertex-colored graphs that are $k$-Tinhofer but not $(k + 1)$-Tinhofer. For every fixed integer $k \ge 0$, the problem of deciding whether a given $k$-Tinhofer graph is ($k + 1$)-Tinhofer is $P$-hard under uniform $\mathsf{AC^0}$ many-one reductions. We show that testing isomorphism between an $(n - k)$-Tinhofer graph $G$ and an arbitrary graph $H$ is fixed-parameter tractable with respect to the parameter $k$.