On monotone circuits with local oracles and clique lower bounds

摘要

We investigate monotone circuits with local oracles [Krají?ek 2016] i.e., circuits containing additional inputs $y_i = y_i(ec{x})$ that can perform unstructured computations on the input string $ec{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(ec{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.