Merlin Oracles, Venkatesan T. Chakaravarthy, Sambuddha Roy
important property of the class PprAM| | is that it can be derandomized as PprAM| | = PNP| | , under a natural hardness hypothesis used for derandomizing the class AM; this directly follows from...
Approximating Maximum Weight K-Colorable Subgraphs in Chordal Graphs (2009)
Venkatesan T. Chakaravarthy, Sambuddha Roy
We present a 2-approximation algorithm for the problem of finding the maximum weight K-colorable subgraph in a given chordal graph with node weights. The running time of the algorithm is O(K(n+m)),...
We show that ACC is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar...
DETERMINISTICALLY ISOLATING A PERFECT MATCHING IN BIPARTITE PLANAR GRAPHS (2008)
Samir Datta, Raghav Kulkarni, Sambuddha Roy
Abstract. We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma...
⋄ Prizes and Scholarships · 4th position in the IIT-Joint Entrance Exam, 1994, held all across India. · 1st position in the statewide Joint Entrance Exam, 1994, held in the state of West Bengal,...
EXP: the missing equivalence 1 Lowness of AM ∩ coAM (2008)
The fact that we will repeatedly use in the following is the result of [Sch89] that AM ∩ coAM exactly capture the low sets for AM. We do not have a similar nice result for MA- if we run through the...
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs (2008)
Datta, Samir, Kulkarni, Raghav, Roy, Sambuddha
We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as...
Venkatesan T, Vinayaka Pandit, Sambuddha Roy, Pranjal Awasthi, Mukesh Mohania
We consider the problem of constructing decision trees for entity identification from a given relational table. The input is a table containing information about a set of entities over a fixed set of...
Planar and Grid Graph Reachability Problems (2008)
Eric Allender, David A. Mix, Barrington Tanmoy, Chakraborty Samir Datta, Sambuddha Roy
We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. In particular, we focus on different classes of planar graphs, of which grid graphs...
Finding Irrefutable Certificates for $S_2^p$ via Arthur and Merlin (2008)
Chakaravarthy, Venkatesan, Roy, Sambuddha
We show that $S_2^p\subseteq P^{prAM}$, where $S_2^p$ is the symmetric alternation class and $prAM$ refers to the promise version of the Arthur-Merlin class $AM$. This is derived as a consequence of...
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs (2008)
Datta, Samir, Kulkarni, Raghav, Roy, Sambuddha
We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as...
Finding Irrefutable Certificates for $S_2^p$ via Arthur and Merlin (2008)
Chakaravarthy, Venkatesan, Roy, Sambuddha
We show that $S_2^p\subseteq P^{prAM}$, where $S_2^p$ is the symmetric alternation class and $prAM$ refers to the promise version of the Arthur-Merlin class $AM$. This is derived as a consequence of...
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs (2008)
Datta, Samir, Kulkarni, Raghav, Roy, Sambuddha
We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as...
15. Finding Irrefutable Certificates for S_2^p via Arthur and Merlin (2008)
Chakaravarthy, Venkatesan T., Roy, Sambuddha
We show that $S_2^psubseteq P^{prAM}$, where $S_2^p$ is the symmetric alternation class and $prAM$ refers to the promise version of the Arthur-Merlin class $AM$. This is derived as a consequence of...
21. Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs (2008)
Datta, Samir, Kulkarni, Raghav, Roy, Sambuddha
We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as...
Eric Allender, Distinguishing Complexity, Sambuddha Roy, Detlef Ronneburger
We continue an investigation of resource-bounded Kolmogorov complexity and derandomization techniques begun in [2, 3]. We introduce nondeterministic time-bounded Kolmogorov complexity measures (KNt...
Grid Graph Reachability Problems (2006)
Eric Allender, David A. Mix, Barrington Tanmoy, Chakraborty Samir Datta, Sambuddha Roy
We study the complexity of restricted versions of stconnectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since • reachability on grid graphs is...
Oblivious symmetric alternation (2006)
Venkatesan T. Chakaravarthy, Sambuddha Roy
1 Introduction The symmetric alternation class (Sp2) was introduced independently by Russelland Sundaram [16] and by Canetti [5]. The class S p 2 contains languages havingan interactive proof system...
Grid Graph Reachability Problems (2006)
Eric Allender, David A. Mix, Barrington Tanmoy, Chakraborty Samir Datta, Sambuddha Roy
We study the complexity of restricted versions of stconnectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since • reachability on grid graphs is...
Oblivious symmetric alternation (2006)
Venkatesan T. Chakaravarthy, Sambuddha Roy
Abstract. We introduce a new class O p
Grid Graph Reachability Problems (2006)
Eric Allender, David A. Mix, Barrington Tanmoy, Chakraborty Samir Datta, Sambuddha Roy
We study the complexity of restricted versions of stconnectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since • reachability on grid graphs is...
A nonuniform lower bound for NEXP (2005)
We try to find the best lower bound for NEXP that we can get given current techniques. We extend the results in [BHY94] and in [FK05].
The directed planar reachability problem (2005)
Eric Allender, Samir Datta, Sambuddha Roy
Abstract. We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is...
The directed planar reachability problem (2005)
Eric Allender, Samir Datta, Sambuddha Roy
Abstract. We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is...
Time-space tradeoffs in the counting hierarchy (2001)
Eric Allender, Michal Kouck ´y, Detlef Ronneburger, Sambuddha Roy
We extend the lower bound techniques of [14], to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjaˇsčiĭ’s theorem from the Boolean setting to...
Time-space tradeoffs in the counting hierarchy (2001)
Eric Allender, Michal Kouck ´y, Detlef Ronneburger, Sambuddha Roy, V Vinay
We extend the lower bound techniques of [17], to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjaˇsčiĭ’s theorem from the Boolean setting to...