Chicago Journal of Theoretical Computer Science

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


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

March 25, 2018


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.

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].

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

DOI: 10.4086/cjtcs.2018.001

[] Volume 2017, Article 2 [] Article 2
[back] Volume 2018 [back] Published articles
[CJCTS home]