All reports by Author Chetan Gupta:

__
TR20-025
| 20th February 2020
__

Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari#### Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

__
TR20-024
| 20th February 2020
__

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari#### Randomized and Symmetric Catalytic Computation

__
TR19-095
| 18th July 2019
__

Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari#### Unambiguous Catalytic Computation

Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari

We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists.

As a consequence, we obtain that deciding whether the ... more >>>

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

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 auxiliary tape during the computation but when it halts auxiliary tape’s initial content must ... more >>>

Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

The catalytic Turing machine is a model of computation defined by Buhrman, Cleve,

Kouck, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing

machine, this model has an extra space which is filled with arbitrary content in addition

to the clean space. In such a model we study ...
more >>>