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).
Categories: cs.CC cs.DM math.CO