Sort by: Order: Results:

  • Das, Bireswar; Scharpfenecker, Patrick; Toran, Jacobo (Elsevier, 2017-04)
    It is well-known that succinct encodings of computational problems – using circuits or formulas to encode large instances – generally result in an exponential complexity blow-up compared to their original complexity. We ...
  • Arvind, V.; Das, Bireswar; Kobler, Johannes; Toda, Seinosuke (Springer, 2015-01)
    We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism, denoted CHI, which has running time (2 b N) O(1), where the parameter b is the maximum size of the color classes of the given ...
  • Arvind, V.; Das, Bireswar; Köbler, Johannes; Kuhnert, Sebastian (Elsevier, 2012-08)
    We show that, for k constant, k -tree isomorphism can be decided in logarithmic space by giving an View the MathML sourceO(klogn) space canonical labeling algorithm. The algorithm computes a unique tree decomposition, ...
  • Das, Bireswar; Datta, Samir; Prajakta, Nimbhorkar (Springer Link, 2013-05)
    Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2 (Jakoby and Tantau in Proceedings of FSTTCS’07: The 27th Annual Conference on Foundations of ...
  • Das, Bireswar; Dasgupta, Anirban; Enduri, Murali Krishna; Reddy, Vinod.I (Elsevier, 2018-11)
    In this paper, we show that for a fixed k, there is an NC algorithm that separates the graphs of rank-width at most k from those with rank-width at least
  • Das, Bireswar; Toran, Jacobo; Wagner, Fabian (Elsevier, 2012-08)
    The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time. We give restricted space algorithms for these problems proving the following ...
  • Allender, Eric; Das, Bireswar (Elsevier, 2017-10)
    We show that every problem in the complexity class (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (). In particular Graph Isomorphism lies in . This is the first theorem ...

Search Digital Repository


My Account