Sambuddha Roy

Research Staff Member, IBM India Research Laboratory, New Delhi.  

Contact :

India Research Laboratory, IBM India Pvt. Ltd.

Plot 4, Phase ii, Block C, Vasant Kunj,
New Delhi 110 070,
India.

email : shombuddho at gmail dot com
alternate email : sambuddha at in dot ibm dot com, samroy at paul dot rutgers dot edu
phone : +91 11 4129 2154[office]

Research :

My current interests are in combinatorial optimization, parity results (and at times a combination of the two).

In combinatorial optimization, my interests center around approximation algorithms, integrality of polyhedra, submodularity etc.

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

Application Material :

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

Conference Publications :

Approximating Decision Trees with Multiway Branches (in pdf),
(with Venkatesan Chakravarthy, Vinayaka Pandit, Yogish Sabharwal) ,  to appear in proceedings of the International Conference on Automata, Languages, and Programming (ICALP), 2009.
Arthur and Merlin as Oracles (in pdf),
(with Venkatesan Chakravarthy) ,  in 33rd Symposium on Mathematical Foundations of Computer Science (MFCS), 2008.
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs (in pdf),
(with Samir Datta, Raghav Kulkarni) ,  in 25th Symposium on Theoretical Aspects of Computer Science (STACS), 2008.
Finding Irrefutable Certificates for $S_2^p$ via Arthur and Merlin (in pdf),
(with Venkatesan Chakravarthy) ,  in 25th Symposium on Theoretical Aspects of Computer Science (STACS), 2008.
Decision Trees for Entity Identification: Approximation Algorithms and Hardness Results (in pdf),
(with Venkatesan Chakravarthy, Vinayaka Pandit, Pranjal Awasthi, Mukesh Mohania) ,  in 26th ACM Symposium on Principles of Database Systems (PODS), 2007.
Parity Problems in Planar Graphs (in pdf),
(with Mark Braverman, Raghav Kulkarni),  in Proc. 22nd Annual IEEE Conference on Computational Complexity, 2007.
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.

Journal Publications:

Approximating Maximum Weight K-Colorable Subgraphs in Chordal Graphs (in pdf),
(with Venkatesan Chakravarthy) ,  to appear in Information Processing Letters (IPL).
Space Efficient Counting in Graphs on Surfaces (in pdf),
(with Mark Braverman, Raghav Kulkarni),  to appear in Computational Complexity.
Decision Trees for Entity Identification: Approximation Algorithms and Hardness Results (in pdf),
(with Venkatesan Chakravarthy, Vinayaka Pandit, Pranjal Awasthi, Mukesh Mohania) ,  to appear in Transactions on Algorithms (TALG).
Grid Graph Reachability Problems (in pdf),
(with Eric Allender, David Barrington, Tanmoy Chakraborty and Samir Datta),  to appear in Theory of Computing Systems (TOCS).

(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 :