3 papers
cs.CC2026
On the Reachability Problem on Monoid-Labelled Undirected Graphs
Nagashri Krishnakumar, Harshil Mittal, Jayalal Sarma
The labelled reachability problem for undirected graphs with edges labelled by elements of a monoid (more generally, groupoids or magmas) captures the classes and $\sf…
cs.CC2026
VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
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. Polynomi…
cs.DS2024
On the Parameterized Complexity of Diverse SAT
Neeldhara Misra, Harshil Mittal, Ashutosh Rai
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 fr…