Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Samir Datta:

TR20-074 | 6th May 2020
Eric Allender, Archit Chauhan, Samir Datta

Depth-First Search in Directed Graphs, Revisited

Revisions: 1 , Comments: 1

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 >>>

TR20-024 | 20th February 2020
Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

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

TR19-039 | 12th March 2019
Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

Planarity, Exclusivity, and Unambiguity

Comments: 1

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 >>>

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

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 >>>

TR13-131 | 17th September 2013
Nikhil Balaji, Samir Datta

Collapsing Exact Arithmetic Hierarchies

Revisions: 1

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 >>>

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

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 >>>

TR11-009 | 21st January 2011
Samir Datta, Gautam Prakriya

Planarity Testing Revisited

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 >>>

TR10-201 | 21st December 2010
Samir Datta, Raghav Kulkarni, Raghunath Tewari

Perfect Matching in Bipartite Planar Graphs is in UL

Revisions: 1

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 >>>

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.

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 >>>

TR10-079 | 28th April 2010
Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran

Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

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 >>>

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

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 >>>

TR09-052 | 2nd May 2009
Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf

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. 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 >>>

TR06-130 | 27th September 2006
Tanmoy Chakraborty, Samir Datta

One-input-face MPCVP is Hard for L, but in LogDCFL

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 >>>

TR05-149 | 7th December 2005
Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

Grid Graph Reachability Problems

Revisions: 1

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 >>>

TR05-148 | 6th December 2005
Eric Allender, Samir Datta, Sambuddha Roy

The Directed Planar Reachability Problem

Revisions: 1

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 >>>

TR04-108 | 24th November 2004
Eric Allender, Samir Datta, Sambuddha Roy

Topology inside NC^1

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 >>>

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

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 >>>

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

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 >>>

TR97-016 | 29th April 1997
Manindra Agrawal, Eric Allender, Samir Datta

On TC^0, AC^0, and Arithmetic Circuits

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 >>>

ISSN 1433-8092 | Imprint