Post answers to questions on the practice final here.

-- Practice Final Questions

 Question 8

 • From the lecture notes on 4/26, 2k+1 repetitions are necessary to set the error rate to less than 1/(2^n)

 • k is 2•ln(2)•(n+1)•(x^-2) where x is the current error rate.  (Slides call it epsilon)

 To solve for the number of repetitions, solve 2k+1 in terms of x

 2 • (2•ln(2)•(n+1)•(n^-2c)) + 1
 =  4•ln(2)•(n+1)•(x^-2) + 1
 =  4•ln(2)(n^-2c) + 4•ln(2)(n^(-2c-1)) + 1

Question 8 • From the lecture notes on 4/26, 2k+1 repetitions are necessary to set the error rate to less than 1/(2^n) • k is 2•ln(2)•(n+1)•(x^-2) where x is the current error rate. (Slides call it epsilon) To solve for the number of repetitions, solve 2k+1 in terms of x 2 • (2•ln(2)•(n+1)•(n^-2c)) + 1 = 4•ln(2)•(n+1)•(x^-2) + 1 = 4•ln(2)(n^-2c) + 4•ln(2)(n^(-2c-1)) + 1

-- Practice Final Questions

Salil,Parth,Kushal 5. ((resource:IMG_3449.JPG|Resource Description for IMG_3449.JPG)) 6. ((resource:IMG_3450.JPG|Resource Description for IMG_3450.JPG)) 7. ((resource:IMG_3451.JPG|Resource Description for IMG_3451.JPG))

-- Practice Final Questions

1. Show that finding the ith bit of multiplication is in logspace. Two inputs x and y can be represented by a logarithmic amount of bits. Calculating the value of the ith bit of the product requires log(y) columns of bits of x (shifted over appropriately, think of grade school multiplication) and the carry from the other i-1 entries. Finding the carry requires calculating the sums of the other columns, which requires a total of i*log(y) bits, which is logspace.

-- Practice Final Questions

Ben, Dhruven, Akshay 9) Set Lower Bound Protocol Conditions: S⊆{0,1}m is a set such that membership in S can be certified. Both parties know a number K. The prover's goal is to convince the verifier that |S|≥K and the verifier should reject with good probability if |S|<K2. Let k be an integer such that 2k−2<K≤2k−1. V: Randomly pick a function h:{0,1}m→{0,1}k from a pairwise independent hash collection Hm,k. Pick y∈R{0,1}k. Send h,y to prover. P: Try to find an x∈S such that h(x)=y. Send such an x to V, together with a certificate that x∈S. V output. If h(x)=y and the certificate validates that x∈S accept. otherwise reject. Examples of Set Lower Bound Protocol: 1. GNI ∈ AM[2] 2. IP[k] ⊆ AM 10) Since for any constant c>0, c⋅nk=o(nk+1), it suffices to show that there is an L∈Σp4 that does not have circuits of size nk+1. We know from the circuit size hierarchy that there is a circuit family of size 10⋅nk+1 not equivalent to any nk+1-sized circuit family. Our language L∈Σp4 is computed as follows: On input x, where |x|=n Existentially guess an encoding of a circuit C of size 10⋅nk+1. Universally check for any encoding of a circuit C' of size nk+1 than can [Existentially guess a string of length n on which C and C' output different values and (universally check for any encoding of a circuit C'' of size at most 10⋅nk+1 lexicographically smaller than C that can existentially guess an encoding of a circuit C''' of size nk+1 and can universally check for any string of length n that C'' and C''' output the same values)] and C accepts x. Lines 3-6 are the conjunction of an NP=Σp1 operation with a Πp3 operation, so will be Πp3. We can merge the universal quantifier in line (2), so that lines 2-6 are Πp3, and there lines 1-7 will be Σp4. Q.E.D. For any k>0, there is an L∈Σp2∩Πp2 that does not have circuits of size O(nk). Proof. We first observe either NP is contained in P/poly or NP is not contained in P/poly. In the latter case, we are done as we could pick L to be a language showing NP is not in P/poly. On the other hand, if NP is contained in P/poly, then we known from Sipser-Gacs-Lauteman that Σp2=Πp2=PH, and so our Σp4 predicate of the previous theorem will in Σp2∩Πp2. Since Σp2∩Πp2 is contained in Σp2 hence proved.

-- Practice Final Questions

Question 2. Alan, Anusha PATH is in SPACE(log^2n) Let G be a graph with n nodes, let x and y be nodes of G and let i >=0. We say that PATH(x,y,i) holds if there is a path from x to y in G of length atmost 2^i. We can compute reachability of any two nodes in G if we determine if PATH(x,y,log n) exists. Input tape is the adjacency matrix. There are two other tapes other than input tape. Assume first tape has(x,y,i) already copied to it. The tape will store several tripes and (x,y,i) will be leftmost. i. i=0, compute PATH(x,y,0) This is possible if x=y. if i=1, check whether there exists 1 edge between x and y. This can be done in log space. ii. for i>0, we can compute PATH(x,y,i) with recursive algorithm. For all nodes z check if PATH(x,z,i-1) and PATH(z,y,i-1) exists. We can generate each z in turn reusing space and perform the test. As there are n nodes, it takes log n bits to store z. If there is a PATH(x,z,i), we replace (x,z,i-1) with (z,y,i-1) At any gien time in computing PATH(x,y,logn) we have atmost log n many triples on the work tape and each triple takes atmost 3 log n which gives us O(log^2n) space.