Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#348686] of Benjamin Rossman

Papers Published

  1. Rossman, B, The monotone complexity of k-clique on random graphs, Siam Journal on Computing, vol. 43 no. 1 (January, 2014), pp. 256-279 [doi]
    (last updated on 2022/05/19)

    Abstract:
    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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320