Not having received a satisfactory response to this question in math.SE, I am asking it here:

In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-monotone circuits that are smaller than monotone circuits for Clique. I’m looking for a reference to these best-known circuits. I would also welcome a sketch of how they work.


closed as off-topic by D.W. Feb 1 at 1:26

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. Please pick one site where you'd like the question to appear. If you posted it on the wrong site, you can delete the copy on the wrong site before posting it on the other site. $\endgroup$ – D.W. Feb 1 at 1:26
  • $\begingroup$ I'm voting to close this question because it was cross-posted. $\endgroup$ – D.W. Feb 1 at 1:26
  • 1
    $\begingroup$ @D.W. I think here the meaning is clear: the smallest circuits solving clique which are known. $\endgroup$ – Yuval Filmus Feb 1 at 6:28