Question 2c

Question 2c

Keren Ganon 09 Nov 2019 16:04

I'm not sure how A is defined: can it randomize r_0 for x_0, and then rendomize a different r_1 for x_1? That is, A isn't defined by a single r, but can randomize r values for every x input? Or is it a single r that defines A?

Because if this is the case then the inequality seems odd to me - when we set an r (the left side of the inequality), we have fewer options for A values then on the right side of it.

Re: Question 2c

nbitansky 09 Nov 2019 17:09

$A$ is a probabilistic non-uniform machine (or circuit if you'd like). [$A(x;r)$] denotes running $A$ on input $x$ using coins $r$. Once the coins are fixed, $A$ is deterministic. The exercise says that when talking about non-uniform distinguishers you can always assume w.l.o.g that they are deterministic —- there exists a non-uniform distinguisher that is at least as good.

Re: Question 2c

Keren Ganon 11 Nov 2019 20:22

So from what I understand, all sessions that can be achieved with a fixed r (the left side) can also happen when randomizing r (the right side), but not the opposite - there could be a session that happens when randomizing r that no fixed r can achieve.

If this is true (and I assume it isn't since it contradicts the claim we want to prove) then it doesn't make sense that a fixed r maximizes the distance, since randomizing r gives us more possible sessions.

What an I missing here?

Re: Question 2c

nbitansky 12 Nov 2019 12:21

I don't know what you mean by a session.
If the claim doesn't make sense to you a good way to understand what you're missing may be to try to disprove it.