Skip to main content

The monotone complexity of k-clique on random graphs

Publication ,  Conference
Rossman, B
Published in: SIAM Journal on Computing
January 1, 2014

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.

Duke Scholars

Published In

SIAM Journal on Computing

DOI

ISSN

0097-5397

Publication Date

January 1, 2014

Volume

43

Issue

1

Start / End Page

256 / 279

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2014). The monotone complexity of k-clique on random graphs. In SIAM Journal on Computing (Vol. 43, pp. 256–279). https://doi.org/10.1137/110839059
Rossman, B. “The monotone complexity of k-clique on random graphs.” In SIAM Journal on Computing, 43:256–79, 2014. https://doi.org/10.1137/110839059.
Rossman B. The monotone complexity of k-clique on random graphs. In: SIAM Journal on Computing. 2014. p. 256–79.
Rossman, B. “The monotone complexity of k-clique on random graphs.” SIAM Journal on Computing, vol. 43, no. 1, 2014, pp. 256–79. Scopus, doi:10.1137/110839059.
Rossman B. The monotone complexity of k-clique on random graphs. SIAM Journal on Computing. 2014. p. 256–279.

Published In

SIAM Journal on Computing

DOI

ISSN

0097-5397

Publication Date

January 1, 2014

Volume

43

Issue

1

Start / End Page

256 / 279

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics