Samir Datta

According to our database, Samir Datta authored at least 64 papers between 1997 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Parallel Complexity of Depth-First-Search and Maximal path.

Archit Chauhan, Samir Datta, M. Praveen

CoRR, June, 2025

A parallel algorithm for the odd two-face shortest k-disjoint path problem.

Srijan Chakraborty, Samir Datta

CoRR, March, 2025

Evaluating Monotone Circuits on Surfaces.

Samir Datta, Chetan Gupta

Proceedings of the WALCOM: Algorithms and Computation, 2025

Revisiting Tree canonization using polynomials.

Vikraman Arvind, Samir Datta, Salman Faris, Asif Khan

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

2024

USSR is in P/poly.

Nikhil Balaji, Samir Datta

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Query Maintenance Under Batch Changes with Small-Depth Circuits.

Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, Thomas Zeume

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs.

Archit Chauhan, Samir Datta, Chetan Gupta, Vimal Raj Sharma

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem.

Vikraman Arvind, Samir Datta, Asif Khan, Shivdutt Sharma, Yadu Vasudev, Shankar Ram Vasudevan

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

2023

Dynamic Planar Embedding Is in DynFO.

Samir Datta, Asif Khan, Anish Mukherjee

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

2022

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

Dynamic Meta-Theorems for Distance and Matching.

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

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles.

Samir Datta, Kishlaya Jaiswal

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Depth-First Search in Directed Planar Graphs, Revisited.

Eric Allender, Archit Chauhan, Samir Datta

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Reachability and Matching in Single Crossing Minor Free Graphs.

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

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

Dynamic Complexity of Expansion.

Samir Datta, Anuj Tawari, Yadu Vasudev

Proceedings of the Computer Science - Theory and Applications, 2021

2020

Depth-First Search in Directed Graphs, Revisited.

Eric Allender, Archit Chauhan, Samir Datta

Electron. Colloquium Comput. Complex., 2020

Dynamic Complexity of Reachability: How Many Changes Can We Handle?

Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, Thomas Zeume

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Randomized and Symmetric Catalytic Computation.

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

Proceedings of the Computer Science - Theory and Applications, 2020

2019

Planarity, Exclusivity, and Unambiguity.

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

Electron. Colloquium Comput. Complex., 2019

2018

Planar Maximum Matching: Towards a Parallel Algorithm.

Samir Datta, Raghav Kulkarni, Ashish Kumar, Anish Mukherjee

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Reachability and Distances under Multiple Changes.

Samir Datta, Anish Mukherjee, Nils Vortmeier, Thomas Zeume

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Shortest k-Disjoint Paths via Determinants.

Samir Datta, Siddharth Iyer, Raghav Kulkarni, Anish Mukherjee

Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

2017

A Strategy for Dynamic Programs: Start over and Muddle Through.

Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, Thomas Zeume

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs.

Samir Datta, Raghav Kulkarni, Anish Mukherjee

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Graph Properties in Node-Query Setting: Effect of Breaking Symmetry.

Nikhil Balaji, Samir Datta, Raghav Kulkarni, Supartha Podder

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

Bounded Treewidth and Space-Efficient Linear Algebra.

Nikhil Balaji, Samir Datta

Proceedings of the Theory and Applications of Models of Computation, 2015

Reachability is in DynFO.

Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Counting Euler Tours in Undirected Bounded Treewidth Graphs.

Nikhil Balaji, Samir Datta, Venkatesh Ganesan

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

Collapsing Exact Arithmetic Hierarchies.

Nikhil Balaji, Samir Datta

Proceedings of the Algorithms and Computation - 8th International Workshop, 2014

Space Complexity of Optimization Problems in Planar Graphs.

Samir Datta, Raghav Kulkarni

Proceedings of the Theory and Applications of Models of Computation, 2014

Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.

Eric Allender, Nikhil Balaji, Samir Datta

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Dynamic Complexity of Directed Reachability and Other Problems.

Samir Datta, William Hesse, Raghav Kulkarni

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Space complexity: what makes planar graphs special?

Samir Datta, Raghav Kulkarni

Bull. EATCS, 2013

Tree-width and Logspace: Determinants and Counting Euler Tours.

Nikhil Balaji, Samir Datta

CoRR, 2013

2012

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

Computing Bits of Algebraic Numbers.

Samir Datta, Rameshwar Pratap

Proceedings of the Theory and Applications of Models of Computation, 2012

Improved Bounds for Bipartite Matching on Surfaces.

Samir Datta, Arjun Gopalan, Raghav Kulkarni, Raghunath Tewari

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

2011

Planarity Testing Revisited.

Samir Datta, Gautam Prakriya

Proceedings of the Theory and Applications of Models of Computation, 2011

Some Tractable Win-Lose Games.

Samir Datta, Nagarajan Krishnamurthy

Proceedings of the Theory and Applications of Models of Computation, 2011

Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs.

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

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Verifying Proofs in Constant Depth.

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

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010

Graph Isomorphism for K_3,3-free and K₅-free graphs is in Log-space.

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

Electron. Colloquium Comput. Complex., 2010

Perfect Matching in Bipartite Planar Graphs is in UL.

Samir Datta, Raghav Kulkarni, Raghunath Tewari

Electron. Colloquium Comput. Complex., 2010

Log-space Algorithms for Paths and Matchings in k-trees.

Bireswar Das, Samir Datta, Prajakta Nimbhorkar

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Counting Classes and the Fine Structure between NC¹ and L.

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

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009

Planar and Grid Graph Reachability Problems.

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

Theory Comput. Syst., 2009

Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Planar Graph Isomorphism is in Log-Space.

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

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

A Log-space Algorithm for Canonization of Planar Graphs

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

CoRR, 2008

Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs.

Samir Datta, Raghav Kulkarni, Sambuddha Roy

Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008

3-connected Planar Graph Isomorphism is in Log-space.

Samir Datta, Nutan Limaye, Prajakta Nimbhorkar

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

2007

Planarity, Determinants, Permanents, and (Unique) Matchings.

Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan

Proceedings of the Computer Science, 2007

2006

One-Input-Face MPCVP Is Hard for L, But in LogDCFL.

Tanmoy Chakraborty, Samir Datta

Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

Grid Graph Reachability Problems.

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

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Ad-Hoc Extensions to the 802.15.3 MAC Protocol.

Samir Datta, Ivan Seskar, Mustafa Demirhan, Siun-Chuon Mau, Dipankar Raychaudhuri

Proceedings of the 2005 International Conference on a World of Wireless, 2005

Distributed Sleep-Scheduling Protocols for Energy Conservation in Wireless Networks.

Rohit Naik, Subir K. Biswas, Samir Datta

Proceedings of the 38th Hawaii International Conference on System Sciences (HICSS-38 2005), 2005

The Directed Planar Reachability Problem.

Eric Allender, Samir Datta, Sambuddha Roy

Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

Topology Inside NC¹.

Eric Allender, Samir Datta, Sambuddha Roy

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Topology inside NC¹

Eric Allender, Samir Datta, Sambuddha Roy

Electron. Colloquium Comput. Complex., 2004

Reducing overhearing energy in 802.11 networks by low-power interface idling.

Subir Kumar Biswas, Samir Datta

Proceedings of the 23rd IEEE International Performance Computing and Communications Conference, 2004

2000

Characterizing Small Depth and Small Space Classes by Operators of Higher Type.

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

Chic. J. Theor. Comput. Sci., 2000

1999

Bounded Depth Arithmetic Circuits: Counting and Closure.

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

Proceedings of the Automata, 1999

1998

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

1997

On TC⁰, AC⁰, and Arithmetic Circuits.

Manindra Agrawal, Eric Allender, Samir Datta

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997