Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Chetan Gupta:

TR22-147 | 10th November 2022
Samir Datta, Chetan Gupta

Evaluating Monotone Circuits on Surfaces

Revisions: 3

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 >>>

TR18-106 | 30th May 2018
Chetan Gupta, Vimalraj Sharma, Raghunath Tewari

Reachability in $O(\log n)$ Genus Graphs is in Unambiguous

Revisions: 1

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.

more >>>

ISSN 1433-8092 | Imprint