All reports by Author Chetan Gupta:

__
TR22-147
| 10th November 2022
__

Samir Datta, Chetan Gupta#### Evaluating Monotone Circuits on Surfaces

Revisions: 3

__
TR18-106
| 30th May 2018
__

Chetan Gupta, Vimalraj Sharma, Raghunath Tewari#### Reachability in $O(\log n)$ Genus Graphs is in Unambiguous

Revisions: 1

Samir Datta, Chetan Gupta

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be ... more >>>

Chetan Gupta, Vimalraj Sharma, Raghunath Tewari

Given the polygonal schema embedding of an $O(log n)$ genus graph $G$ and two vertices

$s$ and $t$ in $G$, we show that deciding if there is a path from $s$ to $t$ in $G$ is in unambiguous

logarithmic space.