Karthik Gajulapalli

activity

20232026

collaborators

Showing 2023Show all

2 papers · 1 filter

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 $…