We prove new upper and lower bounds for the Online Orthogonal Vectors Problem (\(\text{OnlineOV}_{n,d}\)). In this problem, a preprocessing algorithm receives \(n\) vectors \(x_1, \ldots, x_n \in \{0,1\}^d\) and constructs a data structure of size \(S\). A query algorithm subsequently receives a query vector \(q \in \{0,1\}^d\) and in time \(T\) decides whether \(q\) is orthogonal to any of the input vectors \(x_i\).

A problem \(\mathcal{P}\) is considered downward self-reducible, if there exists an efficient algorithm for \(\mathcal{P}\) that is allowed to make queries to only strictly smaller instances of \(\mathcal{P}\). Downward self-reducibility has been well studied in the case of decision problems, and it is well known that any downward self-reducible problem must lie in \(\mathsf{PSPACE}\). Harsha, Mitropolsky and Rosen~[ITCS 2023] initiated the study of downward self reductions in the case of search problems. They showed the following interesting collapse: if a problem is in \(\mathsf{TFNP}\) and is downward self-reducible, then it must be in \(\mathsf{PLS}\). Moreover, if the problem admits a unique solution then it must be in \(\mathsf{UEOPL}\).

We show a nearly optimal lower bound on the length of linear relaxed locally decodable codes (RLDCs). Specifically, we prove that any $q$-query linear RLDC $C\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+Ω(1/q)}$. This bound closely matches the known upper bound of $n = k^{1+O(1/q)}$ by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004). Our proof introduces the notion of robust daisies, which are relaxed sunflowers with pseudorandom structure, and leverages a new spread lemma to extract dense robust daisies from arbitrary distributions.

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$, $\mathrm{NC}^0_k$-AVOID is a special case of AVOID where each output bit of $C$ depends on at most $k$ input bits. While there is a very natural randomized algorithm for AVOID, a deterministic algorithm for the problem would have many interesting consequences. Ren, Santhanam, and Wang (FOCS 2022) and Guruswami, Lyu, and Wang (RANDOM 2022) proved that explicit constructions of functions of high formula complexity, rigid matrices, and optimal linear codes, reduce to $\mathrm{NC}^0_4$-AVOID, thus establishing conditional hardness of the $\mathrm{NC}^0_4$-AVOID problem. On the other hand, $\mathrm{NC}^0_2$-AVOID admits polynomial-time algorithms, leaving the question about the complexity of $\mathrm{NC}^0_3$-AVOID open. We give the first reduction of an explicit construction question to $\mathrm{NC}^0_3$-AVOID. Specifically, we prove that a polynomial-time algorithm (with an $\mathrm{NP}$ oracle) for $\mathrm{NC}^0_3$-AVOID for the case of $m=n+n^{2/3}$ would imply an explicit construction of a rigid matrix, and, thus, a super-linear lower bound on the size of log-depth circuits. We also give deterministic polynomial-time algorithms for all $\mathrm{NC}^0_k$-AVOID problems for $m\geq n^{k-1}/\log(n)$. Prior work required an $\mathrm{NP}$ oracle, and required larger stretch, $m \geq n^{k-1}$.