We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the "random assignment" algorithm. Since the random assignment algorithm is known to give the best approximation algorithm for many optimization problems, we believe that this measure is fundamentally interesting.

We study this measure for the optimization problem, Max-Lin-2, in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2. The main ideas we use in our results are from Fourier analysis and derandomization. We will also mention some algorithmic applications of our results for Max-Lin-2.

This is joint work with Johan Hastad.