#

### Volume 2018

#### Article 1

Published by the Department of Computer Science, The University of Chicago.

#### 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)
**BibTeX** entry for this
article (310 bytes)

Submitted April 24, 2017, revised December 18, 2017,
published March 25, 2018.

Volume 2017, Article 2
Article 2

Volume 2018
Published articles