Monday, February 09, 2009

Are results about actual constants interesting?

Josh Burdick had my course on concrete complexity a long time ago. He still dabbles in the area and recently sent me two manuscripts here and here

He seems to have proven the following:

PROBLEM: Given a 6 vertex graph (via (6 choose 2) Boolean inputs) you want to determine if it has a triangle. If you want to build a circuit for this problem just using NAND gates, how many are required.

PARTIAL ANSWER: The problem requires at least 21 NAND gates. ((6 choose 3), plus one output gate; what you'd probably expect, in other words.)

He has asked me two questions that I toss out to the audience
  1. Is the result correct? (probably) Does it contradict anything known (I doubt that)? Does the proof seem correct? (I think so.)
  2. Is the result interesting? To me this is the more interesting question (or meta-question). Are results about actual concrete numbers interesting? My first answer is only if (1) they lead to more more general results, or (2) use interesting techniques. So the answer may be, using (1), I DON"T KNOW, and (2) may be subjective.


  1. I am suspicious. This is not a small number of gates. A simple version of Razborov's clique argument yields an Omega(n^3/log^4 n) lower bound for monotone circuits on n-vertex graphs (e.g. see Jukna's Extremal Combinatorics book).

  2. I don't care about multiplicative constants, let alone additive constants. :)

  3. I believe the fastest algorithms for finding a triangle in a graph use matrix multiplication. Could it be interesting in this context?

  4. I agree entirely to the statements in the post. However, as Ryan Williams notes in his recent paper "Applying Practice to Theory", the power of small examples cannot be underestimated. Indeed, while the constant 21 itself is not interesting, it would be good to know that for small values of n an optimal circuit for the considered function is the straightforward one.

  5. I hadn't read Ryan Williams' "Applying Practice to Theory", but yes, he seems to be thinking along really similar lines (not exactly the same problem, but using NOR gates is basically the same idea :)

    If the sKizzo solver which they used uses some sort of variable ordering (as BDD solvers do), then, if it gets anywhere on this problem, it might be interesting to see which variable orderings give the shortest/fastest proofs.