default search action
Samir Datta
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c46]Archit Chauhan, Samir Datta, Chetan Gupta, Vimal Raj Sharma:
The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs. MFCS 2024: 43:1-43:16 - [c45]Samir Datta, Asif Khan
, Anish Mukherjee
Query Maintenance Under Batch Changes with Small-Depth Circuits. MFCS 2024: 46:1-46:16 - [c44]Nikhil Balaji
USSR is in P/poly. SOSA 2024: 151-159 - [i50]Archit Chauhan, Samir Datta, Chetan Gupta, Vimal Raj Sharma:
The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs. CoRR abs/2407.00237 (2024) - [i49]Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, Thomas Zeume:
Query maintenance under batch changes with small-depth circuits. CoRR abs/2407.20031 (2024) - [i48]Vikraman Arvind, Samir Datta, Salman Faris, Asif Khan
Revisiting Tree Canonization using polynomials. CoRR abs/2408.10338 (2024) - 2023
- [j15]Eric Allender, Nikhil Balaji
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs. Comput. 12(2): 145-173 (2023) - [c43]Samir Datta, Asif Khan
Dynamic Planar Embedding Is in DynFO. MFCS 2023: 39:1-39:15 - [i47]Samir Datta, Asif Khan, Anish Mukherjee:
Dynamic Planar Embedding is in DynFO. CoRR abs/2307.09473 (2023) - [i46]Vikraman Arvind, Samir Datta, Asif Khan
The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem. CoRR abs/2308.10073 (2023) - [i45]Nikhil Balaji, Samir Datta:
USSR is in P/poly. CoRR abs/2310.19335 (2023) - [i44]Nikhil Balaji, Samir Datta:
USSR is in P/poly. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j14]Eric Allender
Depth-first search in directed planar graphs, revisited. Acta Informatica 59(4): 289-319 (2022) - [j13]Samir Datta
Planar Graph Isomorphism Is in Log-Space. ACM Trans. Comput. Theory 14(2): 8:1-8:33 (2022) - [c42]Samir Datta, Chetan Gupta
Dynamic Meta-Theorems for Distance and Matching. ICALP 2022: 118:1-118:20 - [i43]Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap:
On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs. Electron. Colloquium Comput. Complex. TR22 (2022) - [i42]Samir Datta, Chetan Gupta:
Evaluating Monotone Circuits on Surfaces. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c41]Samir Datta
Dynamic Complexity of Expansion. CSR 2021: 56-77 - [c40]Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee
Reachability and Matching in Single Crossing Minor Free Graphs. FSTTCS 2021: 16:1-16:16 - [c39]Eric Allender, Archit Chauhan, Samir Datta
Depth-First Search in Directed Planar Graphs, Revisited. MFCS 2021: 7:1-7:22 - [c38]Samir Datta
Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles. MFCS 2021: 36:1-36:22 - [i41]Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, Raghunath Tewari:
Reachability and Matching in Single Crossing Minor Free Graphs. CoRR abs/2103.13940 (2021) - [i40]Samir Datta, Kishlaya Jaiswal:
Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles. CoRR abs/2106.00714 (2021) - [i39]Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, Raghunath Tewari:
Dynamic Meta-theorems for Distance and Matching. CoRR abs/2109.01875 (2021) - 2020
- [c37]Samir Datta
Randomized and Symmetric Catalytic Computation. CSR 2020: 211-223 - [c36]Samir Datta
Dynamic Complexity of Reachability: How Many Changes Can We Handle? ICALP 2020: 122:1-122:19 - [i38]Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, Thomas Zeume:
Dynamic complexity of Reachability: How many changes can we handle? CoRR abs/2004.12739 (2020) - [i37]Samir Datta, Anuj Tawari, Yadu Vasudev:
Dynamic Complexity of Expansion. CoRR abs/2008.05728 (2020) - [i36]Eric Allender, Archit Chauhan, Samir Datta:
Depth-First Search in Directed Graphs, Revisited. Electron. Colloquium Comput. Complex. TR20 (2020) - [i35]Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari:
Randomized and Symmetric Catalytic Computation. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j12]Samir Datta
A Strategy for Dynamic Programs: Start over and Muddle through. Log. Methods Comput. Sci. 15(2) (2019) - [i34]Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee:
Planarity, Exclusivity, and Unambiguity. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j11]Samir Datta
Reachability Is in DynFO. J. ACM 65(5): 33:1-33:24 (2018) - [c35]Samir Datta
Shortest k-Disjoint Paths via Determinants. FSTTCS 2018: 19:1-19:21 - [c34]Samir Datta
Reachability and Distances under Multiple Changes. ICALP 2018: 120:1-120:14 - [c33]Samir Datta
Planar Maximum Matching: Towards a Parallel Algorithm. ISAAC 2018: 21:1-21:13 - [i33]Samir Datta, Siddharth Iyer, Raghav Kulkarni, Anish Mukherjee:
Shortest k-Disjoint Paths via Determinants. CoRR abs/1802.01338 (2018) - [i32]Samir Datta, Anish Mukherjee, Nils Vortmeier, Thomas Zeume:
Reachability and Distances under Multiple Changes. CoRR abs/1804.08555 (2018) - 2017
- [c32]Samir Datta
A Strategy for Dynamic Programs: Start over and Muddle Through. ICALP 2017: 98:1-98:14 - [i31]Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, Thomas Zeume:
A Strategy for Dynamic Programs: Start over and Muddle through. CoRR abs/1704.07998 (2017) - 2016
- [c31]Nikhil Balaji
Graph Properties in Node-Query Setting: Effect of Breaking Symmetry. MFCS 2016: 17:1-17:14 - [c30]Samir Datta
Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs. MFCS 2016: 28:1-28:12 - 2015
- [c29]Nikhil Balaji
Counting Euler Tours in Undirected Bounded Treewidth Graphs. FSTTCS 2015: 246-260 - [c28]Samir Datta
Reachability is in DynFO. ICALP (2) 2015: 159-170 - [c27]Nikhil Balaji
Bounded Treewidth and Space-Efficient Linear Algebra. TAMC 2015: 297-308 - [i30]Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume:
Reachability is in DynFO. CoRR abs/1502.07467 (2015) - [i29]Nikhil Balaji, Samir Datta, Venkatesh Ganesan:
Counting Euler Tours in Undirected Bounded Treewidth Graphs. CoRR abs/1510.04035 (2015) - [i28]Nikhil Balaji, Samir Datta, Raghav Kulkarni, Supartha Podder:
Graph properties in node-query setting: effect of breaking symmetry. CoRR abs/1510.08267 (2015) - 2014
- [c26]Samir Datta
Dynamic Complexity of Directed Reachability and Other Problems. ICALP (1) 2014: 356-367 - [c25]Eric Allender
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs. MFCS (2) 2014: 13-24 - [c24]Samir Datta
Space Complexity of Optimization Problems in Planar Graphs. TAMC 2014: 300-311 - [c23]Nikhil Balaji
Collapsing Exact Arithmetic Hierarchies. WALCOM 2014: 273-285 - [i27]Nikhil Balaji, Samir Datta:
Bounded Treewidth and Space-Efficient Linear Algebra. CoRR abs/1412.2470 (2014) - 2013
- [j10]Samir Datta, Raghav Kulkarni:
Space complexity: what makes planar graphs special? Bull. EATCS 109: 35-53 (2013) - [j9]Bireswar Das, Samir Datta
Log-Space Algorithms for Paths and Matchings in k-Trees. Theory Comput. Syst. 53(4): 669-689 (2013) - [j8]Olaf Beyersdorff
Verifying proofs in constant depth. ACM Trans. Comput. Theory 5(1): 2:1-2:23 (2013) - [i26]Nikhil Balaji, Samir Datta:
Tree-width and Logspace: Determinants and Counting Euler Tours. CoRR abs/1312.7468 (2013) - [i25]Eric Allender, Nikhil Balaji, Samir Datta:
Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs. Electron. Colloquium Comput. Complex. TR13 (2013) - [i24]Nikhil Balaji, Samir Datta:
Collapsing Exact Arithmetic Hierarchies. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j7]Samir Datta
Space complexity of perfect matching in bounded genus bipartite graphs. J. Comput. Syst. Sci. 78(3): 765-779 (2012) - [j6]Samir Datta
Counting classes and the fine structure between NC1 and L. Theor. Comput. Sci. 417: 36-49 (2012) - [c22]Samir Datta
Improved Bounds for Bipartite Matching on Surfaces. STACS 2012: 254-265 - [c21]Samir Datta
Computing Bits of Algebraic Numbers. TAMC 2012: 189-201 - [i23]Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer:
Verifying Proofs in Constant Depth. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [c20]Olaf Beyersdorff
Verifying Proofs in Constant Depth. MFCS 2011: 84-95 - [c19]Samir Datta
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. STACS 2011: 579-590 - [c18]Samir Datta
Some Tractable Win-Lose Games. TAMC 2011: 365-376 - [c17]Samir Datta
Planarity Testing Revisited. TAMC 2011: 540-551 - [i22]Samir Datta, Gautam Prakriya:
Planarity Testing Revisited. CoRR abs/1101.2637 (2011) - [i21]Samir Datta, Rameshwar Pratap:
Computing Bits of Algebraic Numbers. CoRR abs/1112.4295 (2011) - [i20]Samir Datta, Gautam Prakriya:
Planarity Testing Revisited. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j5]Samir Datta
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs. Theory Comput. Syst. 47(3): 737-757 (2010) - [j4]Samir Datta
Planarity, Determinants, Permanents, and (Unique) Matchings. ACM Trans. Comput. Theory 1(3): 10:1-10:20 (2010) - [c16]Samir Datta
Counting Classes and the Fine Structure between NC1 and L. MFCS 2010: 306-317 - [c15]Bireswar Das, Samir Datta
Log-space Algorithms for Paths and Matchings in k-trees. STACS 2010: 215-226 - [i19]Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran:
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. CoRR abs/1004.5080 (2010) - [i18]Samir Datta, Nagarajan Krishnamurthy:
Some Tractable Win-Lose Games. CoRR abs/1010.5951 (2010) - [i17]Samir Datta, Raghav Kulkarni, Raghunath Tewari:
Perfect Matching in Bipartite Planar Graphs is in UL. Electron. Colloquium Comput. Complex. TR10 (2010) - [i16]Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran:
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. Electron. Colloquium Comput. Complex. TR10 (2010) - [i15]Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer:
Counting Classes and the Fine Structure between NC1 and L. Electron. Colloquium Comput. Complex. TR10 (2010) - [i14]Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:
Graph Isomorphism for K3,3-free and K5-free graphs is in Log-space. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j3]Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta
Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4): 675-723 (2009) - [c14]Samir Datta
Planar Graph Isomorphism is in Log-Space. CCC 2009: 203-214 - [c13]Samir Datta
Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space. FSTTCS 2009: 145-156 - [i13]Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:
Planar Graph Isomorphism is in Log-Space. Algebraic Methods in Computational Complexity 2009 - [i12]Bireswar Das, Samir Datta, Prajakta Nimbhorkar:
Log-space Algorithms for Paths and Matchings in k-trees. CoRR abs/0912.4602 (2009) - [i11]Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf:
Planar Graph Isomorphism is in Log-space. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [c12]Samir Datta, Nutan Limaye, Prajakta Nimbhorkar:
3-connected Planar Graph Isomorphism is in Log-space. FSTTCS 2008: 155-162 - [c11]Samir Datta, Raghav Kulkarni, Sambuddha Roy:
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs. STACS 2008: 229-240 - [i10]Samir Datta, Raghav Kulkarni, Sambuddha Roy:
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs. CoRR abs/0802.2850 (2008) - [i9]Samir Datta, Nutan Limaye, Prajakta Nimbhorkar:
3-connected Planar Graph Isomorphism is in Log-space. CoRR abs/0806.1041 (2008) - [i8]Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:
A Log-space Algorithm for Canonization of Planar Graphs. CoRR abs/0809.2319 (2008) - 2007
- [c10]Samir Datta
Planarity, Determinants, Permanents, and (Unique) Matchings. CSR 2007: 115-126 - 2006
- [c9]Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta
Grid Graph Reachability Problems. CCC 2006: 299-313 - [c8]Tanmoy Chakraborty, Samir Datta
One-Input-Face MPCVP Is Hard for L, But in LogDCFL. FSTTCS 2006: 57-68 - [i7]Tanmoy Chakraborty, Samir Datta:
One-input-face MPCVP is Hard for L, but in LogDCFL. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c7]Eric Allender, Samir Datta
Topology Inside NC¹. CCC 2005: 298-307 - [c6]Eric Allender, Samir Datta
The Directed Planar Reachability Problem. FSTTCS 2005: 238-249 - [c5]Rohit Naik, Subir K. Biswas, Samir Datta:
Distributed Sleep-Scheduling Protocols for Energy Conservation in Wireless Networks. HICSS 2005 - [c4]Samir Datta
Ad-Hoc Extensions to the 802.15.3 MAC Protocol. WOWMOM 2005: 293-298 - [i6]Eric Allender, Samir Datta, Sambuddha Roy:
The Directed Planar Reachability Problem. Electron. Colloquium Comput. Complex. TR05 (2005) - [i5]Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy:
Grid Graph Reachability Problems. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [c3]Subir Kumar Biswas, Samir Datta:
Reducing overhearing energy in 802.11 networks by low-power interface idling. IPCCC 2004: 695-700 - [i4]Eric Allender, Samir Datta, Sambuddha Roy:
Topology inside NC1. Electron. Colloquium Comput. Complex. TR04 (2004) - 2000
- [j2]Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner:
Characterizing Small Depth and Small Space Classes by Operators of Higher Type. Chic. J. Theor. Comput. Sci. 2000 (2000) - [j1]Manindra Agrawal, Eric Allender, Samir Datta
On TC0, AC0, and Arithmetic Circuits. J. Comput. Syst. Sci. 60(2): 395-421 (2000)
1990 – 1999
- 1999
- [c2]Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta
Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP 1999: 149-158 - [i3]Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh:
Bounded Depth Arithmetic Circuits: Counting and Closure. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [i2]Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner:
Characterizing Small Depth and Small Space Classes by Operators of Higher Types. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [c1]Manindra Agrawal, Eric Allender
On TC0, AC0, and Arithmetic Circuits. CCC 1997: 134-148 - [i1]Manindra Agrawal, Eric Allender, Samir Datta:
On TC0, AC0, and Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR97 (1997)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 21:13 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: