CS 535: Complexity Theory, Fall 2020 Homework 9
Due: 2:00AM, Saturday, December 5, 2020.
Reminder. Homework must be typeset with LATEX preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions by yourself without assistance. You must also identify your collaborators. Assignments missing a collaboration statement will not be accepted. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Problem 1 (Perfect Interactive Proofs). For parameters c, s ≥ 0, define the class MAc,s to consist of Merlin-Arthur interactive proofs with completeness probability c and soundness probability s. That is, a language L ∈ MAc,s if there exists a probabilistic poly-time verifier V and a polynomial m(n) such that
x∈L =⇒ ∃u∈{0,1}m(n) Pr[V(x,u)=1]≥c x∈/L =⇒ ∀u∈{0,1}m(n) Pr[V(x,u)=1]≤s.
Recall that in class we defined MA = MA2/3,1/3.
(a) Prove that MA1,1/3 = MA. That is, we may assume Merlin-Arthur proofs have perfect completeness probability. Hint: Modify the proof of the Sipser-Ga ́cs Theorem (Theorem 7.15). (6 points)
(b) Prove that MA2/3,0 = NP. That is, Merlin-Arthur proofs with perfect soundness are no more powerful than deterministic proofs. (4 points)
(c) *Bonus* Prove the same relationships for general interactive proofs. That is, show that IP1,1/3 = IP and IP2/3,0 = NP.
Problem 2 (Counting k-Colorings). Let G = ([n], E) be a graph on n vertices. A k-coloring of G is a vector of colors (c1,…,cn) ∈ [k]n such that for every edge (i,j) ∈ E, we have ci ̸= cj.
(a) Show that there is a rational polynomial p of degree poly(k, n) such that the number of k-colorings of a graph G is given by
kkk
… p(c1,…,cn). c1=1 c2=1 cn=1
Hint: https://en.wikipedia.org/wiki/Lagrange_polynomial. (4 points)
(b) Modify the sumcheck protocol to show that for every constant k, the language #kCOLD =
{⟨G, t⟩ | G has exactly t k-colorings} ∈ IP. (6 points) 1