All reports by Author Karthik Gajulapalli:

__
TR24-054
| 13th March 2024
__

Karthik Gajulapalli, Alexander Golovnev, Samuel King#### On the Power of Adaptivity for Function Inversion

__
TR24-049
| 7th March 2024
__

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich#### Oblivious Classes Revisited: Lower Bounds and Hierarchies

__
TR23-021
| 9th March 2023
__

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi#### Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms

Revisions: 2

Karthik Gajulapalli, Alexander Golovnev, Samuel King

We study the problem of function inversion with preprocessing where, given a function $f : [N] \to [N]$ and a point $y$ in its image, the goal is to find an $x$ such that $f(x) = y$ using at most $T$ oracle queries to $f$ and $S$ bits of preprocessed ... more >>>

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

In this work we study oblivious complexity classes. Among our results:

1) For each $k \in \mathbb{N}$, we construct an explicit language $L_k \in O_2P$ that cannot be computed by circuits of size $n^k$.

2) We prove a hierarchy theorem for $O_2TIME$. In particular, for any function $t:\mathbb{N} \rightarrow \mathbb{N}$ ...
more >>>

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi

Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit $C\colon\{0,1\}^n\to\{0,1\}^m$, $m>n$, the task is to find a $y\in\{0,1\}^m$ outside the range of $C$. For an integer $k\geq 2$, $NC^0_k$-AVOID is a special case of AVOID where each output bit of $C$ depends on at most $k$ ... more >>>