## Abstract

We prove a lower bound of 2^{Ω((n/log n)1/3)} on the monotone size of an explicit function in monotone-NP (where n is the number of input variables). This is higher than any previous lower bound on the monotone size of a function. The previous best being a lower bound of about 2 ^{Ω(n 1/4)} for Andreev's function, proved in [AlBo87]. Our lower bound is proved by the symmetric version of Razborov's method of approximations. However, we present this method in a new and simpler way: Rather than building approximator functions for all the gates in a circuit, we use a gate elimination argument that is based on a Monotone Switching Lemma. The bound applies for a family of functions, each defined by a construction of a small probability space of c-wise independent random variables.

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

Title of host publication | Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000 |

Pages | 378-387 |

Number of pages | 10 |

DOIs | |

State | Published - Dec 1 2000 |

Externally published | Yes |

Event | 32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, United States Duration: May 21 2000 → May 23 2000 |

### Other

Other | 32nd Annual ACM Symposium on Theory of Computing, STOC 2000 |
---|---|

Country/Territory | United States |

City | Portland, OR |

Period | 5/21/00 → 5/23/00 |

## All Science Journal Classification (ASJC) codes

- Software