Samir Datta

120 papers A* 5A 8B 12C 7Misc 3Journal 69Unranked 16
YearRankTypeTitle / Venue / Authors
2026 J jnl
Unambiguous, Randomized, and Symmetric Catalytic Computation.
ACM Trans. Comput. Theory
Samir Datta, Chetan Gupta, Rahul Jain, Vimalraj Sharma, Raghunath Tewari
2025 J jnl
A parallel algorithm for the odd two-face shortest k-disjoint path problem.
CoRR
Srijan Chakraborty, Samir Datta
2025 J jnl
Derandomizing Isolation In Catalytic Logspace.
CoRR
Vikraman Arvind, Srijan Chakraborty, Samir Datta
2025 B conf
Evaluating Monotone Circuits on Surfaces.
WALCOM
Samir Datta, Chetan Gupta
2025 J jnl
Fast exact algorithms via the Matrix Tree Theorem.
CoRR
Vikraman Arvind, Srijan Chakraborty, Samir Datta, Asif Khan
2025 — conf
Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes.
FSTTCS
Archit Chauhan, Samir Datta, M. Praveen
2025 J jnl
Parallel Complexity of Depth-First-Search and Maximal path.
CoRR
Archit Chauhan, Samir Datta, M. Praveen
2025 — conf
Revisiting Tree canonization using polynomials.
SOSA
Vikraman Arvind, Samir Datta, Salman Faris, Asif Khan
2024 B conf
Query Maintenance Under Batch Changes with Small-Depth Circuits.
MFCS
Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, Thomas Zeume
2024 J jnl
Query maintenance under batch changes with small-depth circuits.
CoRR
Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, Thomas Zeume
2024 J jnl
Revisiting Tree Canonization using polynomials.
CoRR
Vikraman Arvind, Samir Datta, Salman Faris, Asif Khan
2024 B conf
The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs.
MFCS
Archit Chauhan, Samir Datta, Chetan Gupta, Vimal Raj Sharma
2024 J jnl
The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs.
CoRR
Archit Chauhan, Samir Datta, Chetan Gupta, Vimal Raj Sharma
2024 — conf
The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem.
FSTTCS
Vikraman Arvind, Samir Datta, Asif Khan, Shivdutt Sharma, Yadu Vasudev, Shankar Ram Vasudevan
2024 — conf
USSR is in P/poly.
SOSA
Nikhil Balaji, Samir Datta
2023 B conf
Dynamic Planar Embedding Is in DynFO.
MFCS
Samir Datta, Asif Khan, Anish Mukherjee
2023 J jnl
Dynamic Planar Embedding is in DynFO.
CoRR
Samir Datta, Asif Khan, Anish Mukherjee
2023 J jnl
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs.
Comput.
Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap
2023 J jnl
The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem.
CoRR
Vikraman Arvind, Samir Datta, Asif Khan, Shivdutt Sharma, Yadu Vasudev, Shankar Ram Vasudevan
2023 J jnl
USSR is in P/poly.
CoRR
Nikhil Balaji, Samir Datta
2023 J jnl
USSR is in P/poly.
Electron. Colloquium Comput. Complex.
Nikhil Balaji, Samir Datta
2022 J jnl
Depth-first search in directed planar graphs, revisited.
Acta Informatica
Eric Allender, Archit Chauhan, Samir Datta
2022 A* conf
Dynamic Meta-Theorems for Distance and Matching.
ICALP
Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, Raghunath Tewari
2022 J jnl
Evaluating Monotone Circuits on Surfaces.
Electron. Colloquium Comput. Complex.
Samir Datta, Chetan Gupta
2022 J jnl
On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs.
Electron. Colloquium Comput. Complex.
Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap
2022 J jnl
Planar Graph Isomorphism Is in Log-Space.
ACM Trans. Comput. Theory
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2021 B conf
Depth-First Search in Directed Planar Graphs, Revisited.
MFCS
Eric Allender, Archit Chauhan, Samir Datta
2021 Misc conf
Dynamic Complexity of Expansion.
CSR
Samir Datta, Anuj Tawari, Yadu Vasudev
2021 J jnl
Dynamic Meta-theorems for Distance and Matching.
CoRR
Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, Raghunath Tewari
2021 B conf
Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles.
MFCS
Samir Datta, Kishlaya Jaiswal
2021 J jnl
Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles.
CoRR
Samir Datta, Kishlaya Jaiswal
2021 — conf
Reachability and Matching in Single Crossing Minor Free Graphs.
FSTTCS
Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, Raghunath Tewari
2021 J jnl
Reachability and Matching in Single Crossing Minor Free Graphs.
CoRR
Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, Raghunath Tewari
2020 J jnl
Depth-First Search in Directed Graphs, Revisited.
Electron. Colloquium Comput. Complex.
Eric Allender, Archit Chauhan, Samir Datta
2020 J jnl
Dynamic Complexity of Expansion.
CoRR
Samir Datta, Anuj Tawari, Yadu Vasudev
2020 A* conf
Dynamic Complexity of Reachability: How Many Changes Can We Handle?
ICALP
Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, Thomas Zeume
2020 J jnl
Dynamic complexity of Reachability: How many changes can we handle?
CoRR
Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, Thomas Zeume
2020 Misc conf
Randomized and Symmetric Catalytic Computation.
CSR
Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari
2020 J jnl
Randomized and Symmetric Catalytic Computation.
Electron. Colloquium Comput. Complex.
Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari
2019 J jnl
A Strategy for Dynamic Programs: Start over and Muddle through.
Log. Methods Comput. Sci.
Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, Thomas Zeume
2019 J jnl
Planarity, Exclusivity, and Unambiguity.
Electron. Colloquium Comput. Complex.
Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee
2018 B conf
Planar Maximum Matching: Towards a Parallel Algorithm.
ISAAC
Samir Datta, Raghav Kulkarni, Ashish Kumar, Anish Mukherjee
2018 J jnl
Reachability Is in DynFO.
J. ACM
Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume
2018 A* conf
Reachability and Distances under Multiple Changes.
ICALP
Samir Datta, Anish Mukherjee, Nils Vortmeier, Thomas Zeume
2018 J jnl
Reachability and Distances under Multiple Changes.
CoRR
Samir Datta, Anish Mukherjee, Nils Vortmeier, Thomas Zeume
2018 — conf
Shortest k-Disjoint Paths via Determinants.
FSTTCS
Samir Datta, Siddharth Iyer, Raghav Kulkarni, Anish Mukherjee
2018 J jnl
Shortest k-Disjoint Paths via Determinants.
CoRR
Samir Datta, Siddharth Iyer, Raghav Kulkarni, Anish Mukherjee
2017 A* conf
A Strategy for Dynamic Programs: Start over and Muddle Through.
ICALP
Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, Thomas Zeume
2017 J jnl
A Strategy for Dynamic Programs: Start over and Muddle through.
CoRR
Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, Thomas Zeume
2016 B conf
Graph Properties in Node-Query Setting: Effect of Breaking Symmetry.
MFCS
Nikhil Balaji, Samir Datta, Raghav Kulkarni, Supartha Podder
2016 B conf
Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs.
MFCS
Samir Datta, Raghav Kulkarni, Anish Mukherjee
2015 C conf
Bounded Treewidth and Space-Efficient Linear Algebra.
TAMC
Nikhil Balaji, Samir Datta
2015 — conf
Counting Euler Tours in Undirected Bounded Treewidth Graphs.
FSTTCS
Nikhil Balaji, Samir Datta, Venkatesh Ganesan
2015 J jnl
Counting Euler Tours in Undirected Bounded Treewidth Graphs.
CoRR
Nikhil Balaji, Samir Datta, Venkatesh Ganesan
2015 J jnl
Graph properties in node-query setting: effect of breaking symmetry.
CoRR
Nikhil Balaji, Samir Datta, Raghav Kulkarni, Supartha Podder
2015 — conf
Reachability is in DynFO.
ICALP (2)
Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume
2015 J jnl
Reachability is in DynFO.
CoRR
Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume
2014 J jnl
Bounded Treewidth and Space-Efficient Linear Algebra.
CoRR
Nikhil Balaji, Samir Datta
2014 B conf
Collapsing Exact Arithmetic Hierarchies.
WALCOM
Nikhil Balaji, Samir Datta
2014 — conf
Dynamic Complexity of Directed Reachability and Other Problems.
ICALP (1)
Samir Datta, William Hesse, Raghav Kulkarni
2014 — conf
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.
MFCS (2)
Eric Allender, Nikhil Balaji, Samir Datta
2014 C conf
Space Complexity of Optimization Problems in Planar Graphs.
TAMC
Samir Datta, Raghav Kulkarni
2013 J jnl
Collapsing Exact Arithmetic Hierarchies.
Electron. Colloquium Comput. Complex.
Nikhil Balaji, Samir Datta
2013 J jnl
Log-Space Algorithms for Paths and Matchings in k-Trees.
Theory Comput. Syst.
Bireswar Das, Samir Datta, Prajakta Nimbhorkar
2013 J jnl
Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.
Electron. Colloquium Comput. Complex.
Eric Allender, Nikhil Balaji, Samir Datta
2013 J jnl
Space complexity: what makes planar graphs special?
Bull. EATCS
Samir Datta, Raghav Kulkarni
2013 J jnl
Tree-width and Logspace: Determinants and Counting Euler Tours.
CoRR
Nikhil Balaji, Samir Datta
2013 J jnl
Verifying proofs in constant depth.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2012 C conf
Computing Bits of Algebraic Numbers.
TAMC
Samir Datta, Rameshwar Pratap
2012 J jnl
Counting classes and the fine structure between NC
Theor. Comput. Sci.
Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer
2012 A conf
Improved Bounds for Bipartite Matching on Surfaces.
STACS
Samir Datta, Arjun Gopalan, Raghav Kulkarni, Raghunath Tewari
2012 J jnl
Space complexity of perfect matching in bounded genus bipartite graphs.
J. Comput. Syst. Sci.
Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran
2012 J jnl
Verifying Proofs in Constant Depth.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2011 J jnl
Computing Bits of Algebraic Numbers
CoRR
Samir Datta, Rameshwar Pratap
2011 J jnl
Planarity Testing Revisited
CoRR
Samir Datta, Gautam Prakriya
2011 C conf
Planarity Testing Revisited.
TAMC
Samir Datta, Gautam Prakriya
2011 J jnl
Planarity Testing Revisited.
Electron. Colloquium Comput. Complex.
Samir Datta, Gautam Prakriya
2011 C conf
Some Tractable Win-Lose Games.
TAMC
Samir Datta, Nagarajan Krishnamurthy
2011 A conf
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs.
STACS
Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. Variyam Vinodchandran
2011 B conf
Verifying Proofs in Constant Depth.
MFCS
Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer
2010 B conf
Counting Classes and the Fine Structure between NC
MFCS
Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer
2010 J jnl
Counting Classes and the Fine Structure between NC
Electron. Colloquium Comput. Complex.
Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer
2010 J jnl
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs.
Theory Comput. Syst.
Samir Datta, Raghav Kulkarni, Sambuddha Roy
2010 J jnl
Graph Isomorphism for K
Electron. Colloquium Comput. Complex.
Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2010 A conf
Log-space Algorithms for Paths and Matchings in k-trees.
STACS
Bireswar Das, Samir Datta, Prajakta Nimbhorkar
2010 J jnl
Perfect Matching in Bipartite Planar Graphs is in UL.
Electron. Colloquium Comput. Complex.
Samir Datta, Raghav Kulkarni, Raghunath Tewari
2010 J jnl
Planarity, Determinants, Permanents, and (Unique) Matchings.
ACM Trans. Comput. Theory
Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan
2010 J jnl
Some Tractable Win-Lose Games
CoRR
Samir Datta, Nagarajan Krishnamurthy
2010 J jnl
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs
CoRR
Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran
2010 J jnl
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs.
Electron. Colloquium Comput. Complex.
Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran
2009 — conf
Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
FSTTCS
Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2009 J jnl
Log-space Algorithms for Paths and Matchings in k-trees
CoRR
Bireswar Das, Samir Datta, Prajakta Nimbhorkar
2009 A conf
Planar Graph Isomorphism is in Log-Space.
CCC
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2009 — conf
Planar Graph Isomorphism is in Log-Space.
Algebraic Methods in Computational Complexity
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2009 J jnl
Planar Graph Isomorphism is in Log-space.
Electron. Colloquium Comput. Complex.
Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf
2009 J jnl
Planar and Grid Graph Reachability Problems.
Theory Comput. Syst.
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
2008 J jnl
3-connected Planar Graph Isomorphism is in Log-space
CoRR
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar
2008 — conf
3-connected Planar Graph Isomorphism is in Log-space.
FSTTCS
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar
2008 J jnl
A Log-space Algorithm for Canonization of Planar Graphs
CoRR
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner
2008 J jnl
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs
CoRR
Samir Datta, Raghav Kulkarni, Sambuddha Roy
2008 A conf
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs.
STACS
Samir Datta, Raghav Kulkarni, Sambuddha Roy
2007 Misc conf
Planarity, Determinants, Permanents, and (Unique) Matchings.
CSR
Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan
2006 A conf
Grid Graph Reachability Problems.
CCC
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
2006 — conf
One-Input-Face MPCVP Is Hard for L, But in LogDCFL.
FSTTCS
Tanmoy Chakraborty, Samir Datta
2006 J jnl
One-input-face MPCVP is Hard for L, but in LogDCFL.
Electron. Colloquium Comput. Complex.
Tanmoy Chakraborty, Samir Datta
2005 C conf
Ad-Hoc Extensions to the 802.15.3 MAC Protocol.
WOWMOM
Samir Datta, Ivan Seskar, Mustafa Demirhan, Siun-Chuon Mau, Dipankar Raychaudhuri
2005 — conf
Distributed Sleep-Scheduling Protocols for Energy Conservation in Wireless Networks.
HICSS
Rohit Naik, Subir Biswas, Samir Datta
2005 J jnl
Grid Graph Reachability Problems
Electron. Colloquium Comput. Complex.
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
2005 J jnl
The Directed Planar Reachability Problem
Electron. Colloquium Comput. Complex.
Eric Allender, Samir Datta, Sambuddha Roy
2005 — conf
The Directed Planar Reachability Problem.
FSTTCS
Eric Allender, Samir Datta, Sambuddha Roy
2005 A conf
Topology Inside NC¹.
CCC
Eric Allender, Samir Datta, Sambuddha Roy
2004 C conf
Reducing overhearing energy in 802.11 networks by low-power interface idling.
IPCCC
Subir Biswas, Samir Datta
2004 J jnl
Topology inside NC
Electron. Colloquium Comput. Complex.
Eric Allender, Samir Datta, Sambuddha Roy
2000 J jnl
Characterizing Small Depth and Small Space Classes by Operators of Higher Type.
Chic. J. Theor. Comput. Sci.
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
2000 J jnl
On TC
J. Comput. Syst. Sci.
Manindra Agrawal, Eric Allender, Samir Datta
1999 J jnl
Bounded Depth Arithmetic Circuits: Counting and Closure
Electron. Colloquium Comput. Complex.
Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh
1999 A* conf
Bounded Depth Arithmetic Circuits: Counting and Closure.
ICALP
Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh
1998 J jnl
Characterizing Small Depth and Small Space Classes by Operators of Higher Types
Electron. Colloquium Comput. Complex.
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner
1997 A conf
On TC
CCC
Manindra Agrawal, Eric Allender, Samir Datta
1997 J jnl
On TC
Electron. Colloquium Comput. Complex.
Manindra Agrawal, Eric Allender, Samir Datta