All reports by Author Sidhant Saraogi:

__
TR24-061
| 5th April 2024
__

Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi#### Improved Lower Bounds for 3-Query Matching Vector Codes

Revisions: 1

__
TR23-193
| 3rd December 2023
__

Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz#### On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity

__
TR23-021
| 9th March 2023
__

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

Revisions: 2

Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi

A Matching Vector ($\mathbf{MV}$) family modulo a positive integer $m \ge 2$ is a pair of ordered lists $\mathcal{U} = (\mathbf{u}_1, \cdots, \mathbf{u}_K)$ and $\mathcal{V} = (\mathbf{v}_1, \cdots, \mathbf{v}_K)$ where $\mathbf{u}_i, \mathbf{v}_j \in \mathbb{Z}_m^n$ with the following property: for any $i \in [K]$, the inner product $\langle \mathbf{u}_i, \mathbf{v}_i \rangle ... more >>>

Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in ... 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 >>>