Showing 2024Show all
2 papers · 1 filter
cs.CC2024
Revisiting Tree Canonization using polynomials
V. Arvind, Samir Datta, Salman Faris +1
Graph Isomorphism (GI) is a fundamental algorithmic problem. Amongst graph classes for which the computational complexity of GI has been resolved, trees are arguably the most funda…
cs.LO2024
Query maintenance under batch changes with small-depth circuits
Samir Datta, Asif Khan, Anish Mukherjee +3
Which dynamic queries can be maintained efficiently? For constant-size changes, it is known that constant-depth circuits or, equivalently, first-order updates suffice for maintaini…