List of Publications
Note:
As is standard in the theoretical computer science community, author names for papers published in theoretical computer science journals
or conference proceedings are listed in alphabetical order.
Journal Publications
- R. Tripathi, E. Valkanova, and V. Kumar. On Strategy Improvement Algorithms for Simple Stochastic Games. Journal of Discrete Algorithms, 9:263--278, 2011.
[pdf]
- Y. Jiang, K. Tian, X. Shen, J. Zhang, J. Chen, and R. Tripathi. The Complexity of Optimal Job Co-Scheduling on Chip Multiprocessors and Heuristics-Based Solutions. IEEE Transactions on Parallel and Distributed Systems, 22(7):1192--1205, 2011.
[pdf]
- R. Tripathi. The 1-Versus-2 Queries Problem Revisited. Theory of Computing Systems, 46(2):193--221, 2010.
[pdf]
- H. Spakowski and R. Tripathi. Hierarchical Unambiguity. SIAM Journal on Computing, 38(5):2079--2112, 2009.
[pdf]
- M. Thakur and R. Tripathi. Linear Connectivity Problems in Directed Hypergraphs. Theoretical Computer Science, 410(27--29):2592--2618, 2009.
[pdf]
- H. Spakowski and R. Tripathi. On the Power of Unambiguity in Alternating Machines.
Theory of Computing Systems, 41(2):291--326, 2007.
[pdf]
- E. Hemaspaandra, L. Hemaspaandra, S. Radziszowski, and R.
Tripathi. Complexity Results in Graph Reconstruction.
Discrete Applied Mathematics, 155(2):103--118, 2007.
[pdf]
- H. Spakowski and R. Tripathi. LWPP and WPP are Not Uniformly Gap-definable.
Journal of Computer and System Sciences, 72(4):660--689, 2006.
[pdf]
- H. Spakowski, M. Thakur, and R. Tripathi. Quantum and Classical
Complexity Classes: Separations, Collapses, and Closure Properties.
Information and Computation, 200(1):1--34, 2005.
[pdf]
Conference Publications
- T. Alahakoon, R. Tripathi, N. Kourtellis, R. Simha, A. Iamnitchi. K-Path Centrality: A New Centrality Measure in Social Networks.
In Proceedings of the 4'th workshop on Social Network Systems (SNS), 2011.[pdf]
- R. Tripathi, E. Valkanova, and V. Kumar. On Strategy Improvement Algorithms for Simple Stochastic Games.
In Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC), pages 240--251, Springer Verlag, volume 6078 of Lecture Notes in Computer Science, 2010.
[pdf]
- Y. Jian, X. Shen, C. Jie, and R. Tripathi. Analysis and Approximation of Optimal Co-Scheduling on Chip Multiprocessors.
In Proceedings of the 17th International Conference on Parallel Architecures and Compilation Techniques (PACT), pages 220--229, 2008. [pdf]
- R. Tripathi. The 1-versus-2 Queries Problem Revisited.
In Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC), pages 137--147,
Springer-Verlag, volume 4835 of Lecture Notes in Computer Science, 2007.
[pdf]
- R. Tripathi. Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument.
In Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS),
pages 548--558, Springer-Verlag, volume 4708 of Lecture Notes in Computer Science, 2007.
[pdf]
- H. Spakowski and R. Tripathi. Hierarchical Unambiguity.
In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS),
pages 777--788, Springer-Verlag, volume 4162 of Lecture Notes in Computer Science, 2006.
[pdf]
- H. Spakowski and R. Tripathi. On the Power of Unambiguity in Alternating Machines.
In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT),
pages 125--136, Springer-Verlag, volume 3623 of Lecture Notes in Computer Science, 2005.
[pdf]
- M. Thakur and R. Tripathi. On the Complexity of Linear
Connectivity Problems in Directed Hypergraphs. In Proceedings
of the 24th Conference on Foundations of Software Technology and
Theoretical Computer Science (FSTTCS), pages 481--493, Springer-Verlag, volume 3328 of
Lecture Notes in Computer Science, 2004.
[pdf]
- E. Hemaspaandra, L. Hemaspaandra, S. Radziszowski, and R.
Tripathi. Complexity Results in Graph Reconstruction. In Proceedings
of the 29th International Symposium on Mathematical Foundations of Computer
Science (MFCS), pages 287--297, Springer-Verlag, volume 3153 of Lecture
Notes in Computer Science, 2004.
[pdf]
- H. Spakowski and R. Tripathi. Degree Bounds on Polynomials and
Relativization Theory. In Proceedings of the 3rd IFIP International
Conference on Theoretical Computer Science (IFIP-TCS), pages 105--118,
Kluwer Academic Publishers, 2004.
[pdf]
- H. Spakowski, M. Thakur, and R. Tripathi. Quantum and Classical
Complexity Classes: Separations, Collapses, and Closure Properties. In
Proceedings of the 23rd Conference on Foundations of Software Technology
and Theoretical Computer Science (FSTTCS), pages 375--386, Springer-Verlag,
volume 2914 of Lecture Notes in Computer Science, 2003.
[pdf]
Reviews
- Review (with Ravikiran Krishnan) of "Discrete Mathematics in Statistical Physics: Introductory Lectures by M. Loebl,"
Zentralblatt MATH, submitted.
- Review of "Probabilistic Proof Systems: A Primer by O. Goldreich," Zentralblatt MATH, Zbl pre05354495, 2010.
- Review of "Complexity of Counting the Optimal Solutions by M. Hermann and R. Pichler," Mathematical Reviews, submitted.
- Review of "Computational Complexity of Computing a Partial Solution for the Graph Automorphism Problems by T. Nagoya and S. Toda," Mathematical Reviews, V. 2010i, 2010i:68055, 2010.
- Review of "Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem by D. Baumeister and J. Rothe," Mathematical Reviews, V. 2010f, 2010f:68054, 2010.
- Review of "A Rice-Style Theorem for Parallel Automata by T. Hirst," Mathematical Reviews, V. 2009m, 2009m:68097, 2009.
- Review of "Universal Relations and #P-Completeness by H. Fournier and G. Malod," Mathematical Reviews, V. 2009k, 2009k:68072, 2009.
- Review of "The Randomized Communication Complexity of Set Disjointness by J. Hastad and A. Wigderson," Mathematical Reviews, V. 2009f, 2009f:68071, 2009.
- Review of "Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy
by A. Pavan, A. Selman, S. Sengupta, and N. Vinodchandran," Mathematical Reviews, V. 2009b, 2009b:68050, 2009.
Technical Reports
- H. Spakowski and R. Tripathi. Hierarchical Unambiguity.
ACM Computing Research Repository Technical Report cs.CC/0702047, 2007.
- V. Kumar and R. Tripathi. Algorithmic Results in Simple Stochastic Games.
University of Rochester Department of Computer Science Technical Report 855, 2004.
- E. Hemaspaandra, L. Hemaspaandra, S. Radziszowski, and R. Tripathi. Complexity Results in Graph Reconstruction.
University of Rochester Department of Computer Science Technical Report 852, 2004.
(Also appears as ACM Computing Research Repository Technical Report cs.CC/0410021, 2004.)
- H. Spakowski and R. Tripathi.On the Power of Unambiguity in Alternating Machines.
University of Rochester Department of Computer Science Technical Report 851, 2004.
- H. Spakowski and R. Tripathi. Degree Bounds on Polynomials and Relativization Theory.
University of Rochester Department of Computer Science Technical Report 820, 2003.
- M. Thakur and R. Tripathi.Cyclomatic Number of Directed Hypergraphs.
University of Rochester Department of Computer Science Technical Report 814, 2003.
- H. Spakowski, M. Thakur, and R. Tripathi. Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.
University of Rochester Department of Computer Science Technical Report 801, 2003.
Copyright:
The copyrights of papers that appeared in conference proceedings or journals generally belong to the publisher.