Karthik Gajulapalli

activity

20232026

collaborators

6 papers

cs.DS2026

Online Orthogonal Vectors Revisited

Karthik Gajulapalli, Alexander Golovnev, Samuel King +1

We prove new upper and lower bounds for the Online Orthogonal Vectors Problem ( $OnlineOV_{n, d}$ ). In this problem, a preprocessing algorithm receives $n$ vectors $x_1,\ldo…

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 $n \times n$ matrices $A, B$ when their product $A B$ 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 $P$ is considered downward self-reducible, if there exists an efficient algorithm for $P$ that is allowed to make queries to only strictly smaller ins…

cs.DS2023

Matrix Multiplication Verification Using Coding Theory

Huck Bennett, Karthik Gajulapalli, Alexander Golovnev +1

We study the Matrix Multiplication Verification Problem (MMV) where the goal is, given three $n \times n$ matrices $A$ , $B$ , and $C$ as input, to decide whether $A B = C$ . A classic…

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 $C : {0, 1}^{n} \to {0, 1}^{m}$ , $m > n$ , the task is to find a $y \in {0, 1}^{m}$ outside the range of $…