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.)
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.