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
   (last updated on 2024/04/24)

   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.