3 papers
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…
cs.CC2025
Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
Karthik Gajulapalli, Zeyong Li, Ilya Volkovich
In this work we study oblivious complexity classes. These classes capture the power of interactive proofs where the prover(s) are only given the input size rather than the actual i…
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…