3 papers
cs.CC2025
The Structure of In-Place Space-Bounded Computation
James Cook, Surendra Ghentiyala, Ian Mertz +2
In the standard model of computing multi-output functions in logspace (), we are given a read-only tape holding and a logarithmic length worktape, and must print $…
cs.CC2025
Downward self-reducibility in the total function polynomial hierarchy
Karthik Gajulapalli, Surendra Ghentiyala, Zeyong Li +1
A problem is considered downward self-reducible, if there exists an efficient algorithm for that is allowed to make queries to only strictly smaller ins…
cs.CC2025
Hierarchies within TFNP: building blocks and collapses
Surendra Ghentiyala, Zeyong Li
In all well-studied subclasses (e.g. etc.), the canonical complete problem takes as input a polynomial-size circuit $C: \{ 0, 1\}^n \ri…