RJRahul Jain
Rahul Jain
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Rahul Jain has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
Raghunath Tewari
2 shared publications- Samir Datta
Chennai Mathematical Institute
2 shared publications Chetan Gupta
Indian Institute of Technology Kanpur
1 shared publication- Chetan Gupta
Indian Institute of Technology Roorkee
1 shared publication - Raghunath Tewari
Indian Institute of Technology Kanpur
1 shared publication Vimal Raj Sharma
Indian Institute of Technology Kanpur
1 shared publication
Latest Publications
- Open Access
- 23 February 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (1) , 1-21
Unambiguous, Randomized, and Symmetric Catalytic Computation
A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape, which is initially filled with arbitrary content; the machine can read or write on the auxiliary tape during the computation, but it is constrained to halt with the same content in the auxiliary tape as it initially had. This article, studies the power of some natural variants of catalytic Turing machines with \(O(\log n)\) -size work tape and a polynomial-size auxiliary tape. We first define the notion of unambiguous catalytic Turing machines and prove that under a standard derandomization assumption, the class of problems solved by unambiguous catalytic Turing machines is the same as the class of problems solved by nondeterministic catalytic Turing machines. We then introduce the notion of randomized catalytic Turing machines and show that the resulting complexity class \(\mathsf {CBPL}\) is contained in the class \(\mathsf {ZPP}\) . We also explore the notion of symmetricity in the context of catalytic computation and prove that, under the same assumption as before, randomized catalytic Turing machines, symmetric catalytic Turing machines, and deterministic catalytic Turing machines that run in polynomial time are equally powerful.- 23 February 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (1) , 1-21
Open AccessUnambiguous, Randomized, and Symmetric Catalytic Computation
A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape, which is initially filled with arbitrary content; the machine can read or write on the auxiliary tape during the computation, but it is constrained to halt with the same content in the auxiliary tape as it initially had. This article, studies the power of some natural variants of catalytic Turing machines with \(O(\log n)\) -size work tape and a polynomial-size auxiliary tape. We first define the notion of unambiguous catalytic Turing machines and prove that under a standard derandomization assumption, the class of problems solved by unambiguous catalytic Turing machines is the same as the class of problems solved by nondeterministic catalytic Turing machines. We then introduce the notion of randomized catalytic Turing machines and show that the resulting complexity class \(\mathsf {CBPL}\) is contained in the class \(\mathsf {ZPP}\) . We also explore the notion of symmetricity in the context of catalytic computation and prove that, under the same assumption as before, randomized catalytic Turing machines, symmetric catalytic Turing machines, and deterministic catalytic Turing machines that run in polynomial time are equally powerful. - 18 October 2023
- Published by Elsevier in Theoretical Computer Science
- Vol. 982
Space efficient algorithm for solving reachability using tree decomposition and separators
- 18 October 2023
- Published by Elsevier in Theoretical Computer Science
- Vol. 982
Space efficient algorithm for solving reachability using tree decomposition and separators