Definition 1.5. For the purposes of a graph problem with one or more graphs G, an efficient algorithm means that the cost of the algorithm is a polynomial in terms of m = max; |E| and n = max |V| (the exponents cannot depend on m or n). Algorithms with costs $2" and $m" are not efficient, but $mn and $m100 are. You can assume the following conjecture is true for the rest of the round (although no one has proved it yet): Conjecture 1.6. There exists no efficient algorithm in general to determine whether two graphs G and G are isomorphic. We suspect that even though it's easy to check an isomorphism, it's hard to find one. 2 Probabilistically-Checkable Interactive Proofs (31 pts) In mathematics, a proof is generally accepted if the person reading it (a verifier) finds that it is logically consistent and justifies the claims made. However, this is not the only way to prove something. For instance, if a friend claimed to know the winning numbers to a lottery ahead of time and hit the jackpot 5 times in a row, it would generally be acceptable to believe that they have a means of knowing those numbers ahead of time, even if there is a chance that they had simply been lucky in guessing. By asking them to guess more and more lottery numbers, the chances get better and better. Suppose a newly-released, efficient algorithm is claimed to simulate fair dice rolls. In this case, the inten- tion is that each outcome of a die has a chance of occurring. Paula claims that the algorithm is faulty, and each roll will instead always produce the same number. System 2.1. To prove the die-rolling algorithm returns the same result for each roll, Paula does the following. 1. Paula tells Victor what the algorithm will roll. 2. Victor uses the efficient algorithm to simulate the rolls of the die once. 3. If Victor's simulated roll of the dice matches what Paula predicted, he believes her claim that the algorithm produces the same result for each roll. Otherwise, he doesn't believe Paula since her prediction was wrong. In this case, if the algorithm returns the same result for each roll, and Paula knows this result, she should always successfully predict the outcome of the simulated die roll. Consequently, Victor would always believe her. Question 2.1 (2 pts). Suppose the die-rolling algorithm correctly simulates a fair die, returning one of six random outcomes, each with probability. In this case, Paula's claim would be false. Compute the probability that she still correctly predicts the outcome of the simulated roll, which would convince Victor that the die simulation is faulty. Under the right conditions, systems like the one above are probabilistically-checkable interactive proofs. trials and will not believe her in about (1 - p) of those trials. Question 2.4 (5 pts). Suppose that Victor and Paula run a PCIP system S. Find an explicit threshold T where there exists an such that the soundness of REPET(S) is arbitrarily close to 0 and the completeness of REP,T(S) is arbitrarily close to 1. Justify. To illustrate another situation where a PCIP system could be useful, let's tackle a problem similar to Question 1.14. Paula and Victor still have access to two graphs G, G with the same numbers of vertices and edges, but Paula wants to prove that the graphs are NOT isomorphic (this is her statement x). Question 2.5 (3 pts). Explain why our previous algorithm from Question 1.14, of sending the eval- uation table of an isomorphism and checking it, is insufficient for proving that two graphs are NOT isomorphic. Thus, we must turn to a PCIP system. System 2.6. Consider the following system: 1. Victor selects at random one of the two graphs G or G and sends to Paula a random iso- morphic copy of this graph, G'. 2. Upon receiving G', Paula tells Victor which of G or G she thinks G' was copied from (i.e. if she thinks it's Gb, then she sends the number b {1,2}). 3. If Paula tells Victor the correct answer, then Victor believes that G and G are not isomorphic; otherwise, he rejects Paula's proof. Question 2.6 (4 pts). State an efficient procedure to generate an isomorphic copy of a graph uni- formly at random. Assume that you can generate a random number in {1,2, ..., N} for $1. Give the cost of your procedure (still charging the set operations from before). Question 2.7 (3 pts). Suppose Paula wasn't honest and the graphs were actually isomorphic. Ex- plain why Paula has no hope, past random guessing, of figuring out which graph G' came from. However, as is, this isn't quite a PCIP since the completeness and soundness are lacking a bit. Question 2.8 (2 pts). Compute the completeness of this system. That is, if the graphs are not isomorphic and Paula is able to tell them apart, then compute the probability Victor believes this. Question 2.9 (2 pts). Compute the soundness of this system. That is, if the graphs are isomorphic and Paula is lying, then compute the maximum probability Victor believes her. HINT: Paula sends exactly one piece of information to Victor and cannot send anything else. Question 2.10 (3 pts). Explain how to amplify soundness and completeness to the 1/3 and 2/3 thresholds that are necessary, i.e. to make the resulting scheme a PCIP. 3 Zero-Knowledge Proofs (37 pts) System 1.4 provides a way for Paula to prove to Victor that two graphs are isomorphic. However, it requires her to give an isomorphism f to Victor. In some situations, Paula may not necessarily want to Definition 2.2. A probabilistically-checkable interactive proof (PCIP) system is a coordinated algorithm between two players, named Victor and Paula. It consists of back-and-forth communi- cation between the two parties, wherein Paula is trying to prove a statement a to Victor, and Victor can only run efficient algorithms. The completeness of the system is the probability that Victor believes is true given that Paula's claim is actually true. In other words, it measures Paula's ability to prove a true statement to Victor. . Suppose x is false, but Paula is trying to make Victor believe it is true. The soundness of the system is the maximum probability, over all possible strategies of Paula (where she has to send the same messages as if she were honest), that Victor believes Paula. In other words, it measures Victor's ability to avoid believing false statements from Paula. We require that a PCIP satisfies the following properties: 1. The completeness is at least 2/3. 2. The soundness is at most 1/3. For instance, the completeness of System 2.1 is 1, while the soundness of the system is the answer to Question 2.1. System 2.3. Suppose that the dice algorithm from System 2.1 is faulty, but returns the number 3 with probability and the other numbers each of the time. Suppose Paula knows this and makes the claim to Victor that the algorithm has these new probabilities. Paula uses the same procedure as System 2.1, where she always tells Victor that a 3 will be rolled. Question 2.2 (2 pts). Compute the completeness of System 2.3; that is, when the distribution is indeed like this, find the probability that the system succeeds. In fact, the 1/3 and 2/3 values in Definition 2.2 are somewhat arbitrary. Indeed, many other sets of values work, as long as the completeness is greater than the soundness. Definition 2.4. For a PCIP system S, define the repetition system REP,T(S) as the system where the pair repeats the system S times independently (i.e. all randomness between runs is indepen- dent) with a threshold T = [0, 1], where Victor believes Paula overall if he believes her claim after at least Tl of the repetitions. Question 2.3 (5 pts). Compute some T and l such that REPT (System 2.3) has completeness greater than and the soundness less than 3. For large enough l, we can utilize the law of large numbers. Theorem 2.5. The law of large numbers says that when a random experiment (such as a PCIP) is repeated enough times, the fraction of trials that correspond to each possible outcome gets arbitrar- ily close to the probability of that outcome happening. For instance, suppose Victor has a probability p of believing Paula in a PCIP and a probability 1 - p of not believing her. If this PCIP is run for large enough , then Victor will believe Paula in about pl of those