## Abstract

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of size s in a graph m vertices requires monotone circuits of size Ω(m^{ s} /(log m)^{2 s} ) for fixed s, and size m^{ Ω}(log m) for m/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/log m)^{2/3} requires monotone circuits exp (Ω((m/log m)^{1/3})). For fixed s, any monotone circuit that detects cliques of size s requires m)^{ s} ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function of n variables is exp (Ω(n^{ 1/4} · (log n)^{1/2})), improving a recent result of exp (Ω(n^{ 1/8-ε})) due to Andreev.

Original language | English (US) |
---|---|

Pages (from-to) | 1-22 |

Number of pages | 22 |

Journal | Combinatorica |

Volume | 7 |

Issue number | 1 |

DOIs | |

State | Published - Mar 1987 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Keywords

- AMS subject classification (1980): 68E10, 68C25