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 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 $AB = C$. A classic randomized algorithm by Freivalds (MFCS, 1979) solves MMV in $\widetilde{O}(n^2)$ time, and a longstanding challenge is to (partially) derandomize it while still running in faster than matrix multiplication time (i.e., in $o(n^ω)$ time). To that end, we give two algorithms for MMV in the case where $AB - C$ is sparse. Specifically, when $AB - C$ has at most $O(n^δ)$ non-zero entries for a constant $0 \leq δ< 2$, we give (1) a deterministic $O(n^{ω- \varepsilon})$-time algorithm for constant $\varepsilon = \varepsilon(δ) > 0$, and (2) a randomized $\widetilde{O}(n^2)$-time algorithm using $δ/2 \cdot \log_2 n + O(1)$ random bits. The former algorithm is faster than the deterministic algorithm of Künnemann (ESA, 2018) when $δ\geq 1.056$, and the latter algorithm uses fewer random bits than the algorithm of Kimbrel and Sinha (IPL, 1993), which runs in the same time and uses $\log_2 n + O(1)$ random bits (in turn fewer than Freivalds's algorithm). We additionally study the complexity of MMV. We first show that all algorithms in a natural class of deterministic linear algebraic algorithms for MMV (including ours) require $Ω(n^ω)$ time. We also show a barrier to proving a super-quadratic running time lower bound for matrix multiplication (and hence MMV) under the Strong Exponential Time Hypothesis (SETH). Finally, we study relationships between natural variants and special cases of MMV (with respect to deterministic $\widetilde{O}(n^2)$-time reductions).

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}$.

We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted $\mathcal{R}_1$ and $\mathcal{R}_2$. In round $\mathcal{R}_1$, the capacity of each school is fixed and mechanism $\mathcal{M}_1$ finds a student optimal stable matching. In round $\mathcal{R}_2$, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations. It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results, the first simply disallows any re-allocations in round $\mathcal{R}_2$, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable matchings which minimize the number of re-allocations form a sublattice of the lattice of stable matchings. Observations about incentive compatibility are woven into these results. We also give a third type of results, namely proofs of NP-hardness for a mechanism for round $\mathcal{R}_2$ under certain settings.