  We investigate monotone circuits with local oracles [K., 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.
  1. 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$.
  2. 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.
  The second result, which concerns monotone circuits with restricted oracles,
extends and provides a matching upper bound for the exponential lower bounds on
the monotone circuit size complexity of $k$-clique obtained by Alon and Boppana
(1987).
