Samir Datta
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Samir Datta has a total of 42 co-authors. Here are the top co-authors by number of shared publications:
- Anish Mukherjee
University of Warwick, Coventry, United Kingdom
4 shared publications - Raghav Kulkarni
University of Chicago, Chicago, IL, USA
4 shared publications - Eric Allender
Rutgers University, New Brunswick, USA
3 shared publications - Nikhil Balaji
Chennai Mathematical Institute
3 shared publications - Nils Vortmeier
TU Dortmund University Dortmund Germany
3 shared publications - Prajakta Nimbhorkar
Chennai Mathematical Institute, Chennai, India
3 shared publications
Latest Publications
- Open Access
- 23 February 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (1) , 1-21
Unambiguous, Randomized, and Symmetric Catalytic Computation
A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape, which is initially filled with arbitrary content; the machine can read or write on the auxiliary tape during the computation, but it is constrained to halt with the same content in the auxiliary tape as it initially had. This article, studies the power of some natural variants of catalytic Turing machines with \(O(\log n)\) -size work tape and a polynomial-size auxiliary tape. We first define the notion of unambiguous catalytic Turing machines and prove that under a standard derandomization assumption, the class of problems solved by unambiguous catalytic Turing machines is the same as the class of problems solved by nondeterministic catalytic Turing machines. We then introduce the notion of randomized catalytic Turing machines and show that the resulting complexity class \(\mathsf {CBPL}\) is contained in the class \(\mathsf {ZPP}\) . We also explore the notion of symmetricity in the context of catalytic computation and prove that, under the same assumption as before, randomized catalytic Turing machines, symmetric catalytic Turing machines, and deterministic catalytic Turing machines that run in polynomial time are equally powerful.- 23 February 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (1) , 1-21
Open AccessUnambiguous, Randomized, and Symmetric Catalytic Computation
A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape, which is initially filled with arbitrary content; the machine can read or write on the auxiliary tape during the computation, but it is constrained to halt with the same content in the auxiliary tape as it initially had. This article, studies the power of some natural variants of catalytic Turing machines with \(O(\log n)\) -size work tape and a polynomial-size auxiliary tape. We first define the notion of unambiguous catalytic Turing machines and prove that under a standard derandomization assumption, the class of problems solved by unambiguous catalytic Turing machines is the same as the class of problems solved by nondeterministic catalytic Turing machines. We then introduce the notion of randomized catalytic Turing machines and show that the resulting complexity class \(\mathsf {CBPL}\) is contained in the class \(\mathsf {ZPP}\) . We also explore the notion of symmetricity in the context of catalytic computation and prove that, under the same assumption as before, randomized catalytic Turing machines, symmetric catalytic Turing machines, and deterministic catalytic Turing machines that run in polynomial time are equally powerful. - 21 February 2025
- Published by Springer Nature
- p. 127-142
Evaluating Monotone Circuits on Surfaces
- Open Access
USSR is in P/poly
The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers $a_1, \dots, a_k$, and signs $δ_1, \dots, δ_k \in \{-1, 1\}$, check if $\sum_{i=1}^k δ_i \sqrt{a_i} > 0$. The problem is known to have a polynomial time algorithm on the real RAM model of computation, however no sub-exponential time algorithm is known in the bit or Turing model of computation. The precise computational complexity of SSR has been a notorious open problem \cite{ggj} over the last four decades. The problem is known to admit an upper bound in the third level of the \emph{Counting Hierarchy}, i.e., $\CHtwo$ and no non-trivial lower bounds are known. Even when the input numbers are \emph{small}, i.e., given in \emph{unary}, no better complexity bound was known prior to our work. In this paper, we show that the unary variant (USSR) of the sum of square roots problem is considerably easier by giving a $P/poly$ upper bound.Open AccessUSSR is in P/poly
The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers $a_1, \dots, a_k$, and signs $δ_1, \dots, δ_k \in \{-1, 1\}$, check if $\sum_{i=1}^k δ_i \sqrt{a_i} > 0$. The problem is known to have a polynomial time algorithm on the real RAM model of computation, however no sub-exponential time algorithm is known in the bit or Turing model of computation. The precise computational complexity of SSR has been a notorious open problem \cite{ggj} over the last four decades. The problem is known to admit an upper bound in the third level of the \emph{Counting Hierarchy}, i.e., $\CHtwo$ and no non-trivial lower bounds are known. Even when the input numbers are \emph{small}, i.e., given in \emph{unary}, no better complexity bound was known prior to our work. In this paper, we show that the unary variant (USSR) of the sum of square roots problem is considerably easier by giving a $P/poly$ upper bound. - 14 March 2023
- Published by SAGE Publications in Computability
- Vol. 12 (2) , 145-173
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs
We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform TC 0 circuits for
- 14 March 2023
- Published by SAGE Publications in Computability
- Vol. 12 (2) , 145-173
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs
We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform TC 0 circuits for
- Open Access
- 30 June 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 14 (2) , 1-33
Planar Graph Isomorphism Is in Log-Space
Graph Isomorphism is the prime example of a computational problem with a wide difference between the best-known lower and upper bounds on its complexity. The gap between the known upper and lower bounds continues to be very significant for many subclasses of graphs as well.We bridge the gap for a natural and important class of graphs, namely, planar graphs, by presenting a log-space upper bound that matches the known log-space hardness. In fact, we show a stronger result that planar graphcanonizationis in log-space.
- 30 June 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 14 (2) , 1-33
Open AccessPlanar Graph Isomorphism Is in Log-Space
Graph Isomorphism is the prime example of a computational problem with a wide difference between the best-known lower and upper bounds on its complexity. The gap between the known upper and lower bounds continues to be very significant for many subclasses of graphs as well.We bridge the gap for a natural and important class of graphs, namely, planar graphs, by presenting a log-space upper bound that matches the known log-space hardness. In fact, we show a stronger result that planar graphcanonizationis in log-space.
- 4 June 2022
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 289-319
Depth-first search in directed planar graphs, revisited
- 4 June 2022
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 289-319
Depth-first search in directed planar graphs, revisited
- Open Access
Dynamic complexity of Reachability: How many changes can we handle?
In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was extended for changes of size $\frac{\log n}{\log \log n}$, where $n$ is the size of the graph. Changes of polylogarithmic size can be handled when also majority quantifiers may be used. In this paper we extend these results by showing that, for changes of polylogarithmic size, first-order update formulas suffice for maintaining (1) undirected reachability, and (2) directed reachability under insertions. For classes of directed graphs for which efficient parallel algorithms can compute non-zero circulation weights, reachability can be maintained with update formulas that may use "modulo 2" quantifiers under changes of polylogarithmic size. Examples for these classes include the class of planar graphs and graphs with bounded treewidth. The latter is shown here. As the logics we consider cannot maintain reachability under changes of larger sizes, our results are optimal with respect to the size of the changes.Open AccessDynamic complexity of Reachability: How many changes can we handle?
In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was extended for changes of size $\frac{\log n}{\log \log n}$, where $n$ is the size of the graph. Changes of polylogarithmic size can be handled when also majority quantifiers may be used. In this paper we extend these results by showing that, for changes of polylogarithmic size, first-order update formulas suffice for maintaining (1) undirected reachability, and (2) directed reachability under insertions. For classes of directed graphs for which efficient parallel algorithms can compute non-zero circulation weights, reachability can be maintained with update formulas that may use "modulo 2" quantifiers under changes of polylogarithmic size. Examples for these classes include the class of planar graphs and graphs with bounded treewidth. The latter is shown here. As the logics we consider cannot maintain reachability under changes of larger sizes, our results are optimal with respect to the size of the changes. - Open Access
- 8 May 2019
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 15, Is
A Strategy for Dynamic Programs: Start over and Muddle through
In the setting of DynFO, dynamic programs update the stored result of a query whenever the underlying data changes. This update is expressed in terms of first-order logic. We introduce a strategy for constructing dynamic programs that utilises periodic computation of auxiliary data from scratch and the ability to maintain a query for a limited number of change steps. We show that if some program can maintain a query for log n change steps after an AC$^1$-computable initialisation, it can be maintained by a first-order dynamic program as well, i.e., in DynFO. As an application, it is shown that decision and optimisation problems defined by monadic second-order (MSO) formulas are in DynFO, if only change sequences that produce graphs of bounded treewidth are allowed. To establish this result, a Feferman-Vaught-type composition theorem for MSO is established that might be useful in its own right.
- 8 May 2019
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 15, Is
Open AccessA Strategy for Dynamic Programs: Start over and Muddle through
In the setting of DynFO, dynamic programs update the stored result of a query whenever the underlying data changes. This update is expressed in terms of first-order logic. We introduce a strategy for constructing dynamic programs that utilises periodic computation of auxiliary data from scratch and the ability to maintain a query for a limited number of change steps. We show that if some program can maintain a query for log n change steps after an AC$^1$-computable initialisation, it can be maintained by a first-order dynamic program as well, i.e., in DynFO. As an application, it is shown that decision and optimisation problems defined by monadic second-order (MSO) formulas are in DynFO, if only change sequences that produce graphs of bounded treewidth are allowed. To establish this result, a Feferman-Vaught-type composition theorem for MSO is established that might be useful in its own right.
- Open Access
Reachability and Distances under Multiple Changes
Recently it was shown that the transitive closure of a directed graph can be updated using first-order formulas after insertions and deletions of single edges in the dynamic descriptive complexity framework by Dong, Su, and Topor, and Patnaik and Immerman. In other words, Reachability is in DynFO. In this article we extend the framework to changes of multiple edges at a time, and study the Reachability and Distance queries under these changes. We show that the former problem can be maintained in DynFO$(+, \times)$ under changes affecting O($\frac{\log n}{\log \log n}$) nodes, for graphs with $n$ nodes. If the update formulas may use a majority quantifier then both Reachability and Distance can be maintained under changes that affect O($\log^c n$) nodes, for fixed $c \in \mathbb{N}$. Some preliminary results towards showing that distances are in DynFO are discussed.Open AccessReachability and Distances under Multiple Changes
Recently it was shown that the transitive closure of a directed graph can be updated using first-order formulas after insertions and deletions of single edges in the dynamic descriptive complexity framework by Dong, Su, and Topor, and Patnaik and Immerman. In other words, Reachability is in DynFO. In this article we extend the framework to changes of multiple edges at a time, and study the Reachability and Distance queries under these changes. We show that the former problem can be maintained in DynFO$(+, \times)$ under changes affecting O($\frac{\log n}{\log \log n}$) nodes, for graphs with $n$ nodes. If the update formulas may use a majority quantifier then both Reachability and Distance can be maintained under changes that affect O($\log^c n$) nodes, for fixed $c \in \mathbb{N}$. Some preliminary results towards showing that distances are in DynFO are discussed.