Ultimately, though, we are interested in finding a verifier that accepts or rejects C based on a structural explanation of the circuit; our no-coincidence conjecture is our best attempt to formalize that claim, even if it is imperfect.
Can you say more about what made you decide to go with the 99% clause? Did you consider any alternatives?
Reading the post, I also felt like 99% was kind of an arbitrary number. I would have expected it to be something like: for all $\epsilon > 0$ there exists a $V$ such that … $1-\epsilon$ of random circuits satisfy …
I’m hoping more for some stepping stones between the pre-theoretic concept of “structural” and the fully formalized 99%-clause. If we could measure structuralness more directly we should be able to get away with less complexity in the rest of the conjecture.
My suspicion is that we could replace “99%” with “all but exponentially small probability in n”. I also suspect that you could replace it with 1−ε, with the stipulation that the length of π (or the running time of V) will depend on ε. But I’m not exactly sure how I expect it to depend on ε -- for instance, it might be exponential in 1/ε.
My basic intuition is that the closer you make 99% to 1, the smaller the number of circuits that V is allowed to say “look non-random” (i.e. are flagged for some advice π). And so V is forced to do more thorough checks (“is it actually non-random in the sort of way that could lead to P being true?”) before outputting 1.
99% is just a kind-of lazy way to sidestep all of these considerations and state a conjecture that’s “spicy” (many theoretical computer scientists think our conjecture is false) without claiming too much / getting bogged down in the details of how the “all but a small fraction of circuits” thing depends on n or the length of π or the runtime of V.
many theoretical computer scientists think our conjecture is false
Does that mean that you (plural) are either members of a theoretical computer science community or have discussed the conjecture with people that are? (I have no idea who you are or what connections you may or may not have with academia in general.)
Can you say more about what made you decide to go with the 99% clause? Did you consider any alternatives?
Reading the post, I also felt like 99% was kind of an arbitrary number. I would have expected it to be something like: for all $\epsilon > 0$ there exists a $V$ such that … $1-\epsilon$ of random circuits satisfy …
I’m hoping more for some stepping stones between the pre-theoretic concept of “structural” and the fully formalized 99%-clause. If we could measure structuralness more directly we should be able to get away with less complexity in the rest of the conjecture.
Thanks, this is a good question.
My suspicion is that we could replace “99%” with “all but exponentially small probability in n”. I also suspect that you could replace it with 1−ε, with the stipulation that the length of π (or the running time of V) will depend on ε. But I’m not exactly sure how I expect it to depend on ε -- for instance, it might be exponential in 1/ε.
My basic intuition is that the closer you make 99% to 1, the smaller the number of circuits that V is allowed to say “look non-random” (i.e. are flagged for some advice π). And so V is forced to do more thorough checks (“is it actually non-random in the sort of way that could lead to P being true?”) before outputting 1.
99% is just a kind-of lazy way to sidestep all of these considerations and state a conjecture that’s “spicy” (many theoretical computer scientists think our conjecture is false) without claiming too much / getting bogged down in the details of how the “all but a small fraction of circuits” thing depends on n or the length of π or the runtime of V.
Does that mean that you (plural) are either members of a theoretical computer science community or have discussed the conjecture with people that are? (I have no idea who you are or what connections you may or may not have with academia in general.)
Yeah, I did a CS PhD in Columbia’s theory group and have talked about this conjecture with a few TCS professors.
I think I have an idea to make that 99% closer to 1. But its development became too big for a comment here, so I made a post about it.