Minimal achievable approximation ratio for MAX-MQ in finite fields

AbstractGiven a multivariate quadratic polynomial system in a finite field Fq, the problem MAX-MQ is to find a solution satisfying the maximal number of equations. We prove that the probability of a random assignment satisfying a non-degenerate quadratic equation is at least 1q−O(q−n2), where n is the number of the variables in the equation. Consequently, the random assignment provides a polynomial-time approximation algorithm with approximation ratio q+O(q−n2) for non-degenerate MAX-MQ. For large n, the ratio is close to q. According to a result by Håstad, it is NP-hard to approximate MAX-MQ with an approximation ratio of q−ϵ for a small positive number ϵ. Therefore, the minimal approximation ratio that can be achieved in polynomial time for MAX-MQ is q