I was given a HW assignment that asks me the following:
Given a system of $m$ linear equations in variables $x_1,x_2,...,x_n$ over $\mathbb{F_p}$, find a randomized algorithm that find an assignment for all the $x_i$ such that the expected number of equations solved are $m/p$. Then do a derandomization that gives an efficient deterministic algorithm that solves at least $m/p$ of the equations.
A randomized algorithm is easy - assign each variable a value uniformly from $\mathbb{F_p}$, by the principle of deferred decisions each equation is satisfied with a probability at least $1/p$, since there are $m$ equations and by the linearity of the expectation we get the desired result.
I am having difficulty with the second part, I wish to use the method of conditional expectation: choosing an assignment for the first variables then choosing an assignment to the next variable etc', and the expectation at each point is at least $m/p$ so that after $n$ iterations we have assigned all variables and the expected number of satisfied equations is the number of satisfied equations. I have seen this method used for derandomization of MAX-CUT.
My problems making adjustments:
Unlike MAX-CUT - I can only bound the expected number of solved equations by $m/p$ and not calculate the exact expectancy, this gives me problems when trying to figure out the next best assignment since I can't choose one that maximizes the conditional expectancy
Unlike MAX-CUT - Choosing an assignment for some of the variables can determine the value of another variable (e.g choosing $x_1,x_2$ when we have $x_1+x_2+x_3=1$)
I have a suggestion, but I can't manage to prove it works: At iteration $k$ choose an assignment for $x_k$ s.t the number of equations that are false is minimal (that is equations with one free variable that is not assigned a value contradicting the equality such as $x_j=t$ when we assigned $x_j$ a different value)
I would appreciate help analyzing my suggested algorithm or a point in the right direction