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