Samir Datta

According to our database, Samir Datta authored at least 62 papers between 1998 and 2024.

Collaborative distances:

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

2024

Revisiting Tree Canonization using polynomials.

Vikraman Arvind, Samir Datta, Salman Faris, Asif Khan

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

2023

USSR is in P/poly.

Nikhil Balaji, Samir Datta

Electron. Colloquium Comput. Complex., 2023

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

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

Evaluating Monotone Circuits on Surfaces.

Samir Datta, Chetan Gupta

Electron. Colloquium Comput. Complex., 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

Depth-first search in directed planar graphs, revisited.

Eric Allender, Archit Chauhan, Samir Datta

Acta Informatica, 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

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

Randomized and Symmetric Catalytic Computation.

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

Electron. Colloquium Comput. Complex., 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

2019

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

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

Log. Methods Comput. Sci., 2019

Planarity, Exclusivity, and Unambiguity.

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

Electron. Colloquium Comput. Complex., 2019

2018

Reachability Is in DynFO.

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

J. ACM, 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

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

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

Space Complexity of Optimization Problems in Planar Graphs.

Samir Datta, Raghav Kulkarni

Proceedings of the Theory and Applications of Models of Computation, 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

Log-Space Algorithms for Paths and Matchings in k-Trees.

Bireswar Das, Samir Datta, Prajakta Nimbhorkar

Theory Comput. Syst., 2013

Collapsing Exact Arithmetic Hierarchies.

Nikhil Balaji, Samir Datta

Electron. Colloquium Comput. Complex., 2013

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

Eric Allender, Nikhil Balaji, Samir Datta

Electron. Colloquium Comput. Complex., 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

Counting classes and the fine structure between NC¹ and L.

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

Theor. Comput. Sci., 2012

Space complexity of perfect matching in bounded genus bipartite graphs.

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

J. Comput. Syst. Sci., 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

Electron. Colloquium Comput. Complex., 2011

Some Tractable Win-Lose Games.

Samir Datta, Nagarajan Krishnamurthy

Proceedings of the Theory and Applications of Models of Computation, 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

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

Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan

ACM Trans. Comput. Theory, 2010

Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs.

Samir Datta, Raghav Kulkarni, Sambuddha Roy

Theory Comput. Syst., 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

2009

Planar and Grid Graph Reachability Problems.

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

Theory Comput. Syst., 2009

Planar Graph Isomorphism is in Log-space.

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

Electron. Colloquium Comput. Complex., 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

2008

A Log-space Algorithm for Canonization of Planar Graphs

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

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

2006

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

Tanmoy Chakraborty, Samir Datta

Electron. Colloquium Comput. Complex., 2006

2005

Grid Graph Reachability Problems

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

Electron. Colloquium Comput. Complex., 2005

The Directed Planar Reachability Problem

Eric Allender, Samir Datta, Sambuddha Roy

Electron. Colloquium Comput. Complex., 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

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

On TC⁰, AC⁰, and Arithmetic Circuits.

Manindra Agrawal, Eric Allender, Samir Datta

J. Comput. Syst. Sci., 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

Electron. Colloquium Comput. Complex., 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