List of Publications
Important Notes:
The copyrights of papers that appeared in conference proceedings or journals generally belong to the publisher of the conference proceedings or journals.
Authors are listed in the alphabetical order of surnames (i.e., last names) as per convention in mathematical sciences.
Journal Publications
- H. Spakowski and R. Tripathi. On the Power of Unambiguity in Alternating Machines.
Theory of Computing Systems, 41(2):291--326, 2007.
[ps,
pdf]
- E. Hemaspaandra, L. Hemaspaandra, S. Radziszowski, and R.
Tripathi. Complexity Results in Graph Reconstruction.
Discrete Applied Mathematics, 155(2):103--118, 2007.
[ps,
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.
[ps,
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.
[ps,
pdf]
Conference Publications
- R. Tripathi. The 1-versus-2 Queries Problem Revisited.
In Proceedings of the 18th International Symposium on Algorithms and Computation, pages 137-147,
Springer-Verlag, volume 4835 of Lecture Notes in Computer Science, December 2007.
[ps,
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,
pages 548-558, Springer-Verlag, volume 4708 of Lecture Notes in Computer Science, August 2007.
[ps,
pdf]
- H. Spakowski and R. Tripathi. Hierarchical Unambiguity.
In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science,
pages 777-788, Springer-Verlag, volume 4162 of Lecture Notes in Computer Science, August 2006.
[ps,
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,
pages 125-136, Springer-Verlag, volume 3623 of Lecture Notes in Computer Science, August 2005.
[ps,
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, pages 481-493, Springer-Verlag, volume 3328 of
Lecture Notes in Computer Science, December 2004.
[ps,
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, pages 287-297, Springer-Verlag, volume 3153 of Lecture
Notes in Computer Science, August 2004.
[ps,
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, pages 105-118,
Kluwer Academic Publishers, August 2004.
[ps,
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, pages 375-386, Springer-Verlag,
volume 2914 of Lecture Notes in Computer Science, December 2003.
[ps,
pdf]
Technical Reports
- H. Spakowski and R. Tripathi. Hierarchical Unambiguity.
ACM Computing Research Repository Technical Report cs.CC/0702047, February 2007.[ps,
pdf]
- M. Thakur and R. Tripathi. On the Complexity of Linear
Connectivity Problems in Directed Hypergraphs. Technical Report TR-814, Department of Computer Science, University of Rochester, Revised October 2004.[ps,
pdf]
- V. Kumar and R. Tripathi. Algorithmic Results in Simple Stochastic Games.
Technical Report TR-855, Department of Computer Science, University of Rochester, November 2004.
[ps,
pdf]
Submissions.
- H. Spakowski and R. Tripathi. Hierarchical Unambiguity. Submitted for journal publication.
[ps,
pdf]
- M. Thakur and R. Tripathi. Linear Connectivity Problems in Directed Hypergraphs. Submitted for journal publication.
[ps,
pdf]
- R. Tripathi. The 1-versus-2 Queries Problem Revisited. Submitted for journal publication.
[ps,
pdf]