Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR24-049 | 7th March 2024
Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

Oblivious Classes Revisited: Lower Bounds and Hierarchies

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

TR23-021 | 9th March 2023
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi

Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms

Revisions: 2

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

ISSN 1433-8092 | Imprint