CS 263, Spring 2014, Homework 4

Due at the start of class, Thursday, May 1

1. Find an instance of MAX-3-XOR-SAT with as few clauses as possible in which no two clauses are the negations of each other, but not all clauses can be simultaneously satisfied.

2. Recall that an instance of MAX-3-XOR-SAT can be converted into an equivalent instance of MAX-3-SAT by replacing each XOR clause by four OR clauses. In weighted versions of both problems, we may assume that the weights have been normalized in such a way that the weights of all clauses add up to one; when we replace an XOR clause by four OR clauses, we divide its weight evenly.

1. There is a monotonic function f whose input is the normalized weight of a solution to a MAX-3-XOR-SAT instance, and whose output is the normalized weight of a solution to the corresponding MAX-3-SAT instance. What is f?

2. If f is an arbitrary monotonic function from the interval [0,1] to itself, what can you say about the best approximation ratio for approximating the number f(x) where x is the normalized weight of the optimal solution of a given MAX-3-XOR-SAT instance? Recall that it's easy to find solutions that have weight 1/2 − ε for any instance, and hard to tell whether the optimal weight is near 1/2 or near 1.

3. Recall that hard-to-approximate instances of the clique problem are constructed by making a graph whose vertices are the possible accepting runs of a probabilistic proof checker, and whose edges connect runs that could have both been made on the same proof string. As a toy version of this problem, suppose that a particular proof checker takes as input a proof string six bits long, selects three bits of the string (uniformly at random), and accepts if the three selected bits are not all equal to each other. (I.e., it is checking whether this is a good approximate solution to a problem called NAE-3-SAT.)

1. How many vertices and edges does the corresponding clique instance have?

2. How big is the largest clique in the graph?

4. Prove that, for every positive integer k, there exists a number ε > 0, such that unique game instances with k colors can be approximated with approximation ratio at least ε.