Before reversible circuits, we first considered a simpler setting: triangle counting. The no-coincidence principle in that setting turned out to be true, but for a relatively uninteresting reason, because the domain was not rich enough. Nevertheless, I think this result serves as a helpful exercise for people trying to get to grips with our definitions, as well as providing more of the story about how we ended up with our reversible circuits statement.
In the triangle counting setting, we consider the distribution C3(n,p) over undirected 3-partite graphs on 3 groups of n vertices obtained by taking each of the 3n2 possible edges to be present independently with probability p. We take p=Θ(n−0.5), so there are many more edges than vertices, but much fewer than the total number of possible edges.
For a randomly sampled G∼C3(n,Θ(n−0.5)), one can check that the number of triangles in G has mean Θ(n1.5) and variance Θ(n1.5). So if G has Ω(n1.75+ε) triangles, then we consider this to be an “outrageous coincidence”, since this exceeds the mean by Ω(n1+ε) standard deviations. (This is “outrageous” because if the number of triangles were normally distributed with this mean and variance, then the probability of exceeding this for any of the 23n2 possible graphs would tend to zero.) This motivates the following statement, which turns out to be true:
Proposition (No-coincidence principle for triangle counting, p=Θ(n−0.5)).For any ε>0, there is a linear-time verification algorithm V that receives as input:
A 3-partite graph on 3 groups of n vertices, represented as a list of edges
An advice string π
such that:
For all graphs G with Ω(n1.75+ε) triangles, if n is sufficiently large then there exists π with length linear in the number of edges of G such that V(G,π)=1.
For G∼C3(n,Θ(n−0.5)), the probability that there is any π with V(G,π)=1 tends to zero.
(Note that the result would be trivial if we allowed V to run in polynomial time, since it could then directly count the number of triangles, so we need to be more fine-grained than that.)
Dmitry Vaintrob and Aryan Bhatt were able to generalize this result to polygon counting (note that we consider graphs on k groups of n vertices arranged in a cycle, not k-partite graphs in general, so there are kn2 possible edges, not (k2)n2) and to permanents. So we concluded that neither of these settings seemed to be rich enough to produce an interesting no-coincidence principle (even though permanents are #P-hard to compute), and moved on to considering circuits instead.
Hint for polygon counting:
Write the number of polygons as a cyclic trace tr(A1A2…Ak).
Before reversible circuits, we first considered a simpler setting: triangle counting. The no-coincidence principle in that setting turned out to be true, but for a relatively uninteresting reason, because the domain was not rich enough. Nevertheless, I think this result serves as a helpful exercise for people trying to get to grips with our definitions, as well as providing more of the story about how we ended up with our reversible circuits statement.
In the triangle counting setting, we consider the distribution C3(n,p) over undirected 3-partite graphs on 3 groups of n vertices obtained by taking each of the 3n2 possible edges to be present independently with probability p. We take p=Θ(n−0.5), so there are many more edges than vertices, but much fewer than the total number of possible edges.
For a randomly sampled G∼C3(n,Θ(n−0.5)), one can check that the number of triangles in G has mean Θ(n1.5) and variance Θ(n1.5). So if G has Ω(n1.75+ε) triangles, then we consider this to be an “outrageous coincidence”, since this exceeds the mean by Ω(n1+ε) standard deviations. (This is “outrageous” because if the number of triangles were normally distributed with this mean and variance, then the probability of exceeding this for any of the 23n2 possible graphs would tend to zero.) This motivates the following statement, which turns out to be true:
Proposition (No-coincidence principle for triangle counting, p=Θ(n−0.5)). For any ε>0, there is a linear-time verification algorithm V that receives as input:
A 3-partite graph on 3 groups of n vertices, represented as a list of edges
An advice string π
such that:
For all graphs G with Ω(n1.75+ε) triangles, if n is sufficiently large then there exists π with length linear in the number of edges of G such that V(G,π)=1.
For G∼C3(n,Θ(n−0.5)), the probability that there is any π with V(G,π)=1 tends to zero.
(Note that the result would be trivial if we allowed V to run in polynomial time, since it could then directly count the number of triangles, so we need to be more fine-grained than that.)
Dmitry Vaintrob and Aryan Bhatt were able to generalize this result to polygon counting (note that we consider graphs on k groups of n vertices arranged in a cycle, not k-partite graphs in general, so there are kn2 possible edges, not (k2)n2) and to permanents. So we concluded that neither of these settings seemed to be rich enough to produce an interesting no-coincidence principle (even though permanents are #P-hard to compute), and moved on to considering circuits instead.
Hint for polygon counting:
Write the number of polygons as a cyclic trace tr(A1A2…Ak).