4 citations · 13 across the 12 of their papers we have counts for
26 papers
Topology inside NC
Eric Allender, Samir Datta, Arsenii Karnaukhov +3
We show that ACC is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, s…
USSR is in P/poly
Nikhil Balaji, Samir Datta
The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers , and signs , check if $\sum_{…
The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem
V. Arvind, Samir Datta, Asif Khan +3
Let be a finite group given as input by its multiplication table. For a subset of and an element the Cayley Group Membership Problem (denoted CGM) is to check…
Dynamic Planar Embedding is in DynFO
Samir Datta, Asif Khan, Anish Mukherjee
Planar Embedding is a drawing of a graph on the plane such that the edges do not intersect each other except at the vertices. We know that testing the planarity of a graph and comp…
Dynamic Complexity of Group Problems
Samir Datta, Asif Khan, Shivdutt Sharma +2
Dynamic Complexity was introduced by Immerman and Patnaik PI97 in the nineties and has seen a resurgence of interest with the positive resolution of their conjecture on directed re…
Dynamic Meta-theorems for Distance and Matching
Samir Datta, Chetan Gupta, Rahul Jain +3
Reachability, distance, and matching are some of the most fundamental graph problems that have been of particular interest in dynamic complexity theory in recent years [DKMSZ18, DM…