Why is repeating for polynomial time still negligible if one execution has negligible chance?

killertoge

3/1/24, 8:19 AM

Goldreich justifies why we work with the term negligible by saying among other things "events that occur with negligible (in n) probability remain negligible even if the experiment is repeated for polynomially (in n) many times.". Now I want to proof this statement. So I assume we have a problem with a verifiable solution and an algorithm solves it with negligible chances. And repeating this algorithm for polynomially many times still yields negligible chances. The new algorithm fails with probability atleast $(1-\mu(n))$ for some negligible function $\mu$. And in the worse case it fails on all repeated attempts, which has probability atleast $(1-\mu(n))^{poly_1(n)}$. So in all other cases it succeeds which has probability of at most $1-(1-\mu(n))^{poly_1(n)}$. So do I have to proof that the term $1-(1-\mu(n))^{poly_1(n)}$ is negligible?

0 + 3

negligible

Maeher

3/1/24, 8:33 AM

You can make your life much easier by using a union bound to bound the success probability of repeated attempts. You can then apply the definition of a negligible function to derive the statement.

killertoge

3/1/24, 8:40 AM

So if I execute independant poly amount of time and call A_i the succeess at i-th attempt, I can just proof Pr[A_1+A_2+...A_poly]<=Pr[A_1]+Pr[A_2]+...+Pr[A_poly]=negl which is a polynomial time sum of negligible functions? So basically I proof for any poly*negligble=negligible?

Maeher

3/1/24, 11:27 AM

Yes, that would work.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Why is repeating for polynomial time still negligible if one execution has negligible chance?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.