Math @ Duke

Publications [#348686] of Benjamin Rossman
Papers Published
 Rossman, B, The monotone complexity of kclique on random graphs,
Siam Journal on Computing, vol. 43 no. 1
(January, 2014),
pp. 256279 [doi]
(last updated on 2022/05/19)
Abstract: We present lower and upper bounds showing that the averagecase complexity of the kClique 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. 721730] and Amano [Comput. Complexity, 19 (2010), pp. 183210]. © by SIAM.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

