Papers Published
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.