Best-known Boolean Circuits for Clique?

Question

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.

Answer 1

Wikipedia's article on the clique problem contains references to algorithms for this problem. See especially

Friedrich Eisenbrand, Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326(1--3), Oct 2004.

See also the comments to https://cstheory.stackexchange.com/q/36080/5038 for a quick sketch of an algorithm.

All of those are algorithms, but I believe they can be converted to circuits with approximately the same size. The crucial step is the fast matrix multiplication step, and the known algorithms can be converted into circuits of the same size (or are already expressed as circuits). See, e.g., https://complexityzoo.uwaterloo.ca/Complexity_Garden#boolean_matrix_multiplication. For instance, Strassen's algorithm for multiplying two $n\times n$ matrices in fact describes a boolean circuit of size $O(n^{2.807})$ for that problem. See also Chapter 3.6 of Ingo Wegener's The Complexity of Boolean Functions, which describes how to construct efficient Boolean circuits for matrix multiplication. The other parts of the algorithm for finding cliques are straightforward to convert into Boolean circuits; they're expressed in the language of algorithms, because that makes the description easier, but they in fact are straightforward to implement in a circuit of comparable complexity.