Sambuddha Roy

Graduate Student 
Department of Computer Science,
Rutgers University, New Brunswick 

Contact :

Rutgers, The State University of NJ,

110, Frelinghuysen Road,
Piscataway, New Jersey 08854-8019,
USA.

email : samroy at paul dot rutgers dot edu
phone : (732) 445 4467 [office]
Office : Hill 418.

Research :

My broad interest is in computational complexity. Of late, I have gotten interested in computational geometry too. A common thread between
the two is topology - in computational complexity, I am interested in problems (like st-connectivity) which is (say) NL-hard for general
graphs but might be easier for topologically constrained graphs, say planar graphs. In computational geometry, I am interested in Borsuk
Ulam type theorems.

Ph.D. Advisor :
Professor Eric Allender, Rutgers University.
 

Application Material :

CV (in pdf)
Research Statement (in pdf)
Job Talk

Publications :

Parity Problems in Planar Graphs (in pdf),
(with Mark Braverman, Raghav Kulkarni),  in preparation, 2006.
Grid Graph Reachability Problems (in pdf),
(with Eric Allender, David Barrington, Tanmoy Chakraborty and Samir Datta),  in Proc. 21st Annual IEEE Conference on Computational Complexity, 2006.
Oblivious Symmetric Alternation(in pdf),
(with Venkatesan Chakaravarthy ), in 23rd STACS, 2006.
Some Combinatorial and Algorithmic applications of the Borsuk-Ulam theorem,
(with William Steiger ), preliminary abstract in FWCG, 2005.
The directed planar reachability problem,
(with Eric Allender, and Samir Datta), in 25th FSTTCS, 2005.
Topology inside NC1,
(with Eric Allender, and Samir Datta), in Proc. 20th Annual IEEE Conference on Computational Complexity, 2005.
Derandomization and Distinguishing Complexity,
(with Eric Allender, Michal Koucký and Detlef Ronneburger), in Proc. 18th Annual IEEE Conference on Computational Complexity, 2003, pp. 209-220.
Time-Space Tradeoffs in the Counting Hierarchy,
(with Eric Allender, Michal Koucký, Detlef Ronneburger and V. Vinay), in Proc. 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 295-302.

(Unpublished) Shorts:

A nonuniform lower bound for NEXP (in pdf), 2005. Appears partially in Fortnow Klivans : NP with small advice.
EXP : a missing equivalence (in pdf), 2005.

A note on matching problems complete for Logspace classes (in pdf), with Samir Datta, 2005.

Disclaimer: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Offtrack :

The Lighter Side
Photos

Presentations :

Topology inside NC1, at Complexity, San Jose, 2005.

 
Useful Links :

Teaching :