Showing cs.CCShow all
3 papers · 1 filter
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…
cs.CC2023
Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje +1
Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit , , the task is to find a outside the range of $…