In this paper we prove the following two results.
* We show that for any $C \in {mVF, mVP, mVNP}$, $C = \overline{C}$. Here, $mVF, mVP$, and $mVNP$ are monotone variants of $VF, VP$, and $VNP$, respectively. For an algebraic complexity class $C$, $\overline{C}$ denotes the closure of $C$. ... more >>>

Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $k$-face $\sigma$. In an effort to simplify components of the PCP theorem, Goldreich ... more >>>

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work.

Derandomized direct product ... more >>>