@EmilJeřábek could you explain this? Can the precision be increased sufficiently without incurring an extra n-dependent cost?

The graph turnpike problem seems to be related. sciencedirect.com/science/article/abs/pii/S0020019009001021

I see the point that the cost of the queries stays exponential. In practice, though, the size of the largest instance to be solved in the binary search would be multiplied by a poly(n) factor, which would translate to a huge overhead in the oracle runtime. You're just hiding that in the oracle call. Perhaps the question can be phrased better to take all this into account, in which case feel free to edit / suggest edits.

Nice, I didn't think to look for literature on triangle covers. What are some good references on this problem?

@user6584 You are probably referring to the results on $(k,\epsilon)$-extractors (Theorem 1.9). In this language, my question can be restated as: how badly, in terms of variation distance, will a function fail to be a $(k,\epsilon)$-extractor if $d$ is too low / $m$ is too high?

He's already commented on it: scottaaronson.blog/?p=6405#comment-1939064 scottaaronson.blog/?p=6405#comment-1939221

@MohammadAl-Turkistany Are there any known results on the complexity of counting Hamilton cycles in solid grid graphs?

I don’t see that equation defining treewidth using a tree embedding. I see it defining treewidth using a tree decomposition.