The monotone complexity of k-clique on random graphs

Published

Conference Paper

We present lower and upper bounds showing that the average-case complexity of the k-Clique problem on monotone circuits is nk/4+O(1). Similar bounds for AC0 circuits were shown in Rossman [Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 721-730] and Amano [Comput. Complexity, 19 (2010), pp. 183-210]. © by SIAM.

Full Text

Duke Authors

Cited Authors

  • Rossman, B

Published Date

  • January 1, 2014

Published In

Volume / Issue

  • 43 / 1

Start / End Page

  • 256 - 279

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/110839059

Citation Source

  • Scopus