### Volume 2018

#### On monotone circuits with local oracles and clique lower bounds

Jan Krajíček
Faculty of Mathematics and Physics
Charles University
Czech Republic
krajicek AT karlin DOT mff DOT cuni DOT cz

and

Igor C. Oliveira
Department of Computer Science
University of Oxford
UK
igor.carbonioliveira AT cs DOT ox DOT ac DOT uk

March 25, 2018

#### Abstract

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.
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 in [Alon and Boppana, 1987].

• The article: PDF (293 KB)
• Source material: ZIP (88 KB)