51.A parallel algorithm for the odd two-face shortest k-disjoint path problem.
Srijan Chakraborty, Samir Datta — CoRR — 2025
50.Parallel Complexity of Depth-First-Search and Maximal path.
Archit Chauhan, Samir Datta, M. Praveen — CoRR — 2025
49.Query maintenance under batch changes with small-depth circuits.
Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, Thomas Zeume — CoRR — 2024
48.Revisiting Tree Canonization using polynomials.
Vikraman Arvind, Samir Datta, Salman Faris, Asif Khan — CoRR — 2024
47.The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs.
Archit Chauhan, Samir Datta, Chetan Gupta, Vimal Raj Sharma — CoRR — 2024
45.The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem.
Vikraman Arvind, Samir Datta, Asif Khan, Shivdutt Sharma, Yadu Vasudev, Shankar Ram Vasudevan — CoRR — 2023
43.USSR is in P/poly.
Nikhil Balaji, Samir Datta — Electron. Colloquium Comput. Complex. — 2023
42.Evaluating Monotone Circuits on Surfaces.
Samir Datta, Chetan Gupta — Electron. Colloquium Comput. Complex. — 2022
41.On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs.
Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap — Electron. Colloquium Comput. Complex. — 2022
40.Dynamic Meta-theorems for Distance and Matching.
Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, Raghunath Tewari — CoRR — 2021
39.Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles.
Samir Datta, Kishlaya Jaiswal — CoRR — 2021
38.Reachability and Matching in Single Crossing Minor Free Graphs.
Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, Raghunath Tewari — CoRR — 2021
37.Depth-First Search in Directed Graphs, Revisited.
Eric Allender, Archit Chauhan, Samir Datta — Electron. Colloquium Comput. Complex. — 2020
35.Dynamic complexity of Reachability: How many changes can we handle?
Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, Thomas Zeume — CoRR — 2020
34.Randomized and Symmetric Catalytic Computation.
Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari — Electron. Colloquium Comput. Complex. — 2020
33.Planarity, Exclusivity, and Unambiguity.
Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee — Electron. Colloquium Comput. Complex. — 2019
32.Reachability and Distances under Multiple Changes.
Samir Datta, Anish Mukherjee, Nils Vortmeier, Thomas Zeume — CoRR — 2018
31.Shortest k-Disjoint Paths via Determinants.
Samir Datta, Siddharth Iyer, Raghav Kulkarni, Anish Mukherjee — CoRR — 2018
30.A Strategy for Dynamic Programs: Start over and Muddle through.
Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, Thomas Zeume — CoRR — 2017
29.Counting Euler Tours in Undirected Bounded Treewidth Graphs.
Nikhil Balaji, Samir Datta, Venkatesh Ganesan — CoRR — 2015
28.Graph properties in node-query setting: effect of breaking symmetry.
Nikhil Balaji, Samir Datta, Raghav Kulkarni, Supartha Podder — CoRR — 2015
27.Reachability is in DynFO.
Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume — CoRR — 2015
26.Bounded Treewidth and Space-Efficient Linear Algebra.
Nikhil Balaji, Samir Datta — CoRR — 2014
25.Collapsing Exact Arithmetic Hierarchies.
Nikhil Balaji, Samir Datta — Electron. Colloquium Comput. Complex. — 2013
24.Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.
Eric Allender, Nikhil Balaji, Samir Datta — Electron. Colloquium Comput. Complex. — 2013
23.Tree-width and Logspace: Determinants and Counting Euler Tours.
Nikhil Balaji, Samir Datta — CoRR — 2013
22.Verifying Proofs in Constant Depth.
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer — Electron. Colloquium Comput. Complex. — 2012
19.Planarity Testing Revisited.
Samir Datta, Gautam Prakriya — Electron. Colloquium Comput. Complex. — 2011
18.Counting Classes and the Fine Structure between NC1 and L.
Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer — Electron. Colloquium Comput. Complex. — 2010
17.Graph Isomorphism for K3,3-free and K5-free graphs is in Log-space.
Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner — Electron. Colloquium Comput. Complex. — 2010
16.Perfect Matching in Bipartite Planar Graphs is in UL.
Samir Datta, Raghav Kulkarni, Raghunath Tewari — Electron. Colloquium Comput. Complex. — 2010
14.Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs
Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran — CoRR — 2010
13.Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs.
Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran — Electron. Colloquium Comput. Complex. — 2010
12.Log-space Algorithms for Paths and Matchings in k-trees
Bireswar Das, Samir Datta, Prajakta Nimbhorkar — CoRR — 2009
11.Planar Graph Isomorphism is in Log-space.
Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf — Electron. Colloquium Comput. Complex. — 2009
10.3-connected Planar Graph Isomorphism is in Log-space
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar — CoRR — 2008
9.A Log-space Algorithm for Canonization of Planar Graphs
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner — CoRR — 2008
8.Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs
Samir Datta, Raghav Kulkarni, Sambuddha Roy — CoRR — 2008
7.One-input-face MPCVP is Hard for L, but in LogDCFL.
Tanmoy Chakraborty, Samir Datta — Electron. Colloquium Comput. Complex. — 2006
6.Grid Graph Reachability Problems
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy — Electron. Colloquium Comput. Complex. — 2005
5.The Directed Planar Reachability Problem
Eric Allender, Samir Datta, Sambuddha Roy — Electron. Colloquium Comput. Complex. — 2005
4.Topology inside NC1
Eric Allender, Samir Datta, Sambuddha Roy — Electron. Colloquium Comput. Complex. — 2004
3.Bounded Depth Arithmetic Circuits: Counting and Closure
Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh — Electron. Colloquium Comput. Complex. — 1999
2.Characterizing Small Depth and Small Space Classes by Operators of Higher Types
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner — Electron. Colloquium Comput. Complex. — 1998
1.On TC0, AC0, and Arithmetic Circuits
Manindra Agrawal, Eric Allender, Samir Datta — Electron. Colloquium Comput. Complex. — 1997