We investigate monotone circuits with local oracles [Krajíček 2016] i.e., circuits containing additional inputs $y_i = y_i(\vec{x})$ that can perform unstructured computations on the input string $\vec{x}$. Let $\mu \in [0,1]$ be the locality of the circuit, a parameter that bounds the combined strength of the oracle functions $y_i(\vec{x})$, and $U_{n,k}, V_{n,k} \subseteq \{0,1\}^m$ be the set of $k$-cliques and the set of complete $(k-1)$-partite graphs, respectively (similarly to [Razborov, 1985]).} Our results can be informally stated as follows.

• (i) For an appropriate extension of depth-$2$ monotone circuits with local oracles, we show that the size of the smallest circuits separating $U_{n,3}$ (triangles) and $V_{n,3}$ (complete bipartite graphs) undergoes two phase transitions according to $\mu$.
• (ii) For $5 \leq k(n) \leq n^{1/4}$, arbitrary depth, and $\mu \leq 1/50$, we prove that the monotone circuit size complexity of separating the sets $U_{n,k}$ and $V_{n,k}$ is $n^{\Theta(\sqrt{k})}$, under a certain restrictive assumption on the local oracle gates.

Given a MAX-2-SAT instance, we define a local maximum to be an assignment such that changing any single variable reduces the number of satisfied clauses. We consider the question of the number of local maxima that an instance of MAX-2-SAT can have. We give upper bounds in both the sparse and nonsparse case, where the sparse case means that ther\ e is a bound d on the average number of clauses involving any given variable. The bounds in the nonsparse case are tight up to polylogarithmic factors, while in the sparse case the bounds are tight up to a multiplicative factor in d for large d. Additionally, we generalize to the question of assignments which are maxima up to changing f k> 1 variables simultaneously; in this case, we give explicit constructions with large (in a sense explained below) numbers of such maxima in the spar\ se case. The basic idea of the upper bound proof is to consider a random assignment to some subset of the \ variables and determine the probability that some fraction of the remaining variables can be fixed \ without considering interactions between them. The bounded results hold in the case of weighted MAX-2-SAT as well. Using this technique and combining with ideas from [Golovnev and Kutzkov], we find an algorithm f\ or weighted MAX-2-SAT which is faster for large d than previous algorithms which use polynomial space; this algorithm does require additio\ nal bounds on maximum weights and degree.

We initiate a study of ``universal locally testable codes'' (ULTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a ULTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \left\{ f_i : \{0,1\}^k \to \{0,1\} \right\}_{i \in [M]}$ is a code such that for every $\ i \in [M]$ the subcode $\{ C(x) \: : \: f_i(x) = 1 \}$ is locally testable. We show a ``canonical' $O(1)$-local ULTC of length $\tilde O(M\cdot s)$ for any family $\mathcal{F}$ of $M$ functions such that every $f\in\mathcal{F}$ can be computed by a circuit of size $s$, and establish a lower bound of the form $n\ =M^{1/O(k)}$, which can be strengthened to $n=M^{\Omega(1)}$ for any $\mathcal{F}$ suc\ h that every $f,f' \in\mathcal{F}$ disagree on a constant fraction of their domain

Several variants of nonlocal games have been considered in the study of quantum entanglement and nonlocality. This paper concerns two of these variants, called quantum-classical games and extended nonlocal games. We give a construction of an extended nonlocal game from any quantum-classical game that allows one to translate certain facts concerning quantum-classical games to extended nonlocal games. In particular, based on work of Regev and Vidick, we conclude that there exist extended nonlocal games for which no finite-dimensional entangled strategy can be optimal. While this conclusion is a direct consequence of recent work of Slofstra, who proved a stronger, analogous result for ordinary (non-extended) nonlocal games, the proof based on our construction is considerably simpler, and the construction itself might potentially have other applications in the study of entanglement and nonlocality.

We show that the border support rank of the tensor corresponding to two-by-two matrix multiplication is seven over the complex numbers. We do this by constructing two polynomials that vanish on all complex tensors with format four-by-four-by-four and border rank at most six, but that do not vanish simultaneously on any tensor with the same support as the two-by-two matrix multiplication tensor. This extends the work of Hauenstein, Ikenmeyer, and Landsberg. We also give two proofs that the support rank of the two-by-two matrix multiplication tensor is seven over any field: one proof using a result of De Groote saying that the decomposition of this tensor is unique up to sandwiching, and another proof via the substitution method. These results answer a question asked by Cohn and Umans. Studying the border support rank of the matrix multiplication tensor is relevant for the design of matrix multiplication algorithms, because upper bounds on the border support rank of the matrix multiplication tensor lead to upper bounds on the computational complexity of matrix multiplication, via a construction of Cohn and Umans. Moreover, support rank may be interpreted as a quantum communication complexity measure.