All reports by Author Samir Datta:

__
TR23-163
| 30th October 2023
__

Nikhil Balaji, Samir Datta#### USSR is in P/poly

__
TR22-147
| 10th November 2022
__

Samir Datta, Chetan Gupta#### Evaluating Monotone Circuits on Surfaces

Revisions: 3

__
TR22-053
| 24th April 2022
__

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap#### On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs

Revisions: 3
,
Comments: 1

__
TR20-074
| 6th May 2020
__

Eric Allender, Archit Chauhan, Samir Datta#### Depth-First Search in Directed Graphs, Revisited

Revisions: 3
,
Comments: 1

__
TR20-024
| 20th February 2020
__

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari#### Randomized and Symmetric Catalytic Computation

__
TR19-039
| 12th March 2019
__

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee#### Planarity, Exclusivity, and Unambiguity

Comments: 1

__
TR13-177
| 10th December 2013
__

Eric Allender, Nikhil Balaji, Samir Datta#### Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

Revisions: 1

__
TR13-131
| 17th September 2013
__

Nikhil Balaji, Samir Datta#### Collapsing Exact Arithmetic Hierarchies

Revisions: 1

__
TR12-079
| 14th June 2012
__

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer#### Verifying Proofs in Constant Depth

__
TR11-009
| 21st January 2011
__

Samir Datta, Gautam Prakriya#### Planarity Testing Revisited

__
TR10-201
| 21st December 2010
__

Samir Datta, Raghav Kulkarni, Raghunath Tewari#### Perfect Matching in Bipartite Planar Graphs is in UL

Revisions: 1

__
TR10-101
| 25th June 2010
__

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer#### Counting Classes and the Fine Structure between NC$^1$ and L.

__
TR10-079
| 28th April 2010
__

Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran#### Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

__
TR10-050
| 25th March 2010
__

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner#### Graph Isomorphism for $K_{3,3}$-free and $K_5$-free graphs is in Log-space

__
TR09-052
| 2nd May 2009
__

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf#### Planar Graph Isomorphism is in Log-space

__
TR06-130
| 27th September 2006
__

Tanmoy Chakraborty, Samir Datta#### One-input-face MPCVP is Hard for L, but in LogDCFL

__
TR05-149
| 7th December 2005
__

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy#### Grid Graph Reachability Problems

Revisions: 1

__
TR05-148
| 6th December 2005
__

Eric Allender, Samir Datta, Sambuddha Roy#### The Directed Planar Reachability Problem

Revisions: 1

__
TR04-108
| 24th November 2004
__

Eric Allender, Samir Datta, Sambuddha Roy#### Topology inside NC^1

__
TR99-012
| 19th April 1999
__

Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh#### Bounded Depth Arithmetic Circuits: Counting and Closure

Comments: 1

__
TR98-057
| 10th September 1998
__

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner#### Characterizing Small Depth and Small Space Classes by Operators of Higher Types

__
TR97-016
| 29th April 1997
__

Manindra Agrawal, Eric Allender, Samir Datta#### On TC^0, AC^0, and Arithmetic Circuits

Nikhil Balaji, Samir Datta

The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers $a_1, \dots, a_k$, and signs $\delta_1, \dots, \delta_k \in \{-1, 1\}$, check if $\sum_{i=1}^k \delta_i \sqrt{a_i} > 0$. The problem is known to have a polynomial time algorithm on the real RAM model of computation, ... more >>>

Samir Datta, Chetan Gupta

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be ... more >>>

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

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 division, matrix powering, and related problems, where the improvement is in terms of ...
more >>>

Eric Allender, Archit Chauhan, Samir Datta

We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm ... more >>>

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

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 auxiliary tape during the computation but when it halts auxiliary tape’s initial content must ... more >>>

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

We provide new upper bounds on the complexity of the s-t-connectivity problem in planar graphs, thereby providing additional evidence that this problem is not complete for NL. This also yields a new upper bound on the complexity of computing edit distance. Building on these techniques, we provide new upper bounds ... more >>>

Eric Allender, Nikhil Balaji, Samir Datta

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of ``majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>>

Nikhil Balaji, Samir Datta

We provide a uniform framework for proving the collapse of the hierarchy, $NC^1(\mathcal{C})$

for an exact arithmetic class $\mathcal{C}$ of polynomial degree. These hierarchies collapses all the way down to the third level of the ${AC}^0$-hierarchy, ${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes \[\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.\]

more >>>

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

Samir Datta, Gautam Prakriya

Planarity Testing is the problem of determining whether a given graph is planar while planar embedding is the corresponding construction problem.

The bounded space complexity of these problems has been determined to be Logspace by Allender and Mahajan with the aid of Reingold's result . Unfortunately, the algorithm is quite ...
more >>>

Samir Datta, Raghav Kulkarni, Raghunath Tewari

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon

the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space

complexity bounds for some related problems. Summarizing, we show that, constructing:

1. a Perfect Matching in bipartite planar graphs is in ...
more >>>

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran

We investigate the space complexity of certain perfect matching

problems over bipartite graphs embedded on surfaces of constant genus

(orientable or non-orientable). We show that the problems of deciding

whether such graphs have (1) a perfect matching or not and (2) a

unique perfect matching or not, are in the ...
more >>>

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

Graph isomorphism is an important and widely studied computational problem, with

a yet unsettled complexity.

However, the exact complexity is known for isomorphism of various classes of

graphs. Recently [DLN$^+$09] proved that planar graph isomorphism is complete for log-space.

We extend this result of [DLN$^+$09] further

to the ...
more >>>

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf

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. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and ... more >>>

Tanmoy Chakraborty, Samir Datta

A monotone planar circuit (MPC) is a Boolean circuit that can be

embedded in a plane, and that has only AND and OR

gates. Yang showed that the one-input-face

monotone planar circuit value problem (MPCVP) is in NC^2, and

Limaye et. al. improved the bound to ...
more >>>

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since

* reachability on grid graphs is logspace-equivalent to reachability in general planar digraphs, and

* reachability on certain classes of grid graphs gives ...
more >>>

Eric Allender, Samir Datta, Sambuddha Roy

We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to ... more >>>

Eric Allender, Samir Datta, Sambuddha Roy

We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model.

We consider other generalizations of ...
more >>>

Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

Constant-depth arithmetic circuits have been defined and studied

in [AAD97,ABL98]; these circuits yield the function classes #AC^0

and GapAC^0. These function classes in turn provide new

characterizations of the computational power of threshold circuits,

and provide a link between the circuit classes AC^0 ...
more >>>

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Motivated by the question of how to define an analog of interactive

proofs in the setting of logarithmic time- and space-bounded

computation, we study complexity classes defined in terms of

operators quantifying over oracles. We obtain new

characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ...
more >>>

Manindra Agrawal, Eric Allender, Samir Datta

Continuing a line of investigation that has studied the

function classes #P, #SAC^1, #L, and #NC^1, we study the

class of functions #AC^0. One way to define #AC^0 is as the

class of functions computed by constant-depth polynomial-size

arithmetic circuits of unbounded fan-in addition ...
more >>>