Definition 1.5. For the purposes of a graph problem with one or more graphs G, an...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
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 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
Expert Answer:
Related Book For
Statistics For Business And Financial Economics
ISBN: 9781461458975
3rd Edition
Authors: Cheng Few Lee , John C Lee , Alice C Lee
Posted Date:
Students also viewed these algorithms questions
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
Q1. You have identified a market opportunity for home media players that would cater for older members of the population. Many older people have difficulty in understanding the operating principles...
-
The following data represent the concentration of dissolved organic carbon (mg/L) collected from 20 samples of organic soil. Assume that the population is normally distributed. Complete parts (a)...
-
Why has the IT leadership role in organizations become so important? What are some of the IT service trade-off decisions that IT leaders face today? Why is it important for IT staff to behave as...
-
What do you understand under the term of peer-to-peer lending?
-
The case study that involved balancing a gas turbine that could not pass through its first critical frequency called for use of the existing proximity probe outputs input into a digital FFT using...
-
Published income statements use the absorption-costing basisafter all, that is the method that is acceptable for use under GAAP. But the absorption-costing statement might not really provide the...
-
Tarrant Amertex Regional Hospital, one of our hospitals in the Fort Worth area, has been in need of a new Chief Executive Officer. Last week, we reached a "handshake" dealthough per current protocols...
-
A clique of an undirected graph is a set C of vertices such that for any two vertices u, v in C, there is an edge between u and v. For example, in the below graph, {1,2,4,6} is a clique of size 4,...
-
An S corporation has the following information: Compute the S$ corporation's taxable income for the year. Sales Dividend income Tax-exempt interest Long-term capital gain Short-term capital gain Cost...
-
For a completely transposed three-phase line identical conductors, each with GMR denoted \(\mathrm{D}_{\mathrm{S}}\) with conductor distance \(\mathrm{D}_{12}, \mathrm{D}_{23}\), and...
-
For a single-phase two-conductor line with composite conductors \(x\) and \(y\), express the inductance of conductor \(x\) in terms of GMD and its GMR.
-
If the distance between conductors are large compared to the distances between subconductors of each conductor, then the GMD between conductors is approximately equal to the distance between...
-
Expand \(6 \sqrt{\Pi_{k=1}^{3} \Pi_{m=1^{\prime}}^{2^{\prime}} \mathrm{D}_{k m}}\).
-
Consider the circle C = {z : |2 - 1| = 1/2}, followed in the positive (anticlockwise) direction with initial point z = 1/2. Evaluate the integral dz c (22 - 1)1/2 (22 given that the integrand is...
-
Feller Company purchased a site for a limestone quarry for $100,000 on January 2, 2019. It estimate that the quarry will yield 400,000 tons of limestone. It estimates that its retirement obligation...
-
Suppose a random variable Y is best described by a uniform distribution with a = 3 and b = 32. (a) Find f(y). (b) Find F(y). (c) Find the mean and variance of Y.
-
Briefly explain what a cumulative distribution function is. Give some examples of occasions when the cumulative distribution function is useful.
-
What is the CML? What is the SML? How are they similar? How are they different?
-
Figure 4 shows a scatterplot for the variables life expectancy and infant mortality in 16 countries. What type of correlation does it show? Does this correlation make sense? Does it imply causality?...
-
Figure 5 shows a scatterplot for the variables number of farms and mean farm size in the United States. Each dot represents data from a single year between 1950 and 2000; on this diagram, the earlier...
-
The scatterplots in Figure 6 show two weeks of data comparing the actual high temperature for the day with the same-day forecast (part a) and the three-day forecast (part b). Estimate the correlation...
Study smarter with the SolutionInn App