All reports by Author Sambuddha Roy:

__
TR09-055
| 10th June 2009
__

Venkatesan Chakaravarthy, Sambuddha Roy#### Arthur and Merlin as Oracles

__
TR09-051
| 2nd July 2009
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy#### The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory

__
TR07-035
| 3rd April 2007
__

Mark Braverman, Raghav Kulkarni, Sambuddha Roy#### Parity Problems in Planar Graphs

__
TR05-149
| 7th December 2005
__

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy#### Grid Graph Reachability Problems

Revisions: 1

__
TR05-148
| 6th December 2005
__

Eric Allender, Samir Datta, Sambuddha Roy#### The Directed Planar Reachability Problem

Revisions: 1

__
TR04-108
| 24th November 2004
__

Eric Allender, Samir Datta, Sambuddha Roy#### Topology inside NC^1

__
TR01-041
| 23rd May 2001
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V. Vinay#### Time-Space Tradeoffs in the Counting Hierarchy

Venkatesan Chakaravarthy, Sambuddha Roy

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class.

Our main results are the following: (i) $BPP^{NP}_{||} \subseteq P^{prAM}_{||}$; (ii) $S_2^p \subseteq P^{prAM}$. In addition to providing new upperbounds for the classes $S_2^p$ and $BPP^{NP}_{||}$, these results are interesting ...
more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.

The Kolmogorov measures that have been ...
more >>>

Mark Braverman, Raghav Kulkarni, Sambuddha Roy

We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2^k, for constant k. ... more >>>

Eric Allender, David 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. Grid graphs are a useful tool in this regard, since

* reachability on grid graphs is logspace-equivalent to reachability in general planar digraphs, and

* reachability on certain classes of grid graphs gives ...
more >>>

Eric Allender, Samir Datta, Sambuddha Roy

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 logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to ... more >>>

Eric Allender, Samir Datta, Sambuddha Roy

We show that ACC^0 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 constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model.

We consider other generalizations of ...
more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V. Vinay

We extend the lower bound techniques of [Fortnow], to the

unbounded-error probabilistic model. A key step in the argument

is a generalization of Nepomnjascii's theorem from the Boolean

setting to the arithmetic setting. This generalization is made

possible, due to the recent discovery of logspace-uniform TC^0

more >>>