3 papers
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.DS2025
Output-Sparse Matrix Multiplication Using Compressed Sensing
Huck Bennett, Karthik Gajulapalli, Alexander Golovnev +1
We give two algorithms for output-sparse matrix multiplication (OSMM), the problem of multiplying two matrices when their product is promised to have at mo…
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…