Finding efficient randomized algorithm

Question

I'm doing a course on randomized algorithms and I've encountered a question that I'm struggling to solve.

Given a system of $m$ linear equations with $n$ variables over finite field $\mathbb{F_2}$ where every equation is of form $a_1x_1+...+a_nx_n=b \mod 2$ and $x_i,a_i,b\in\{0,1\}$ and multiplication and sum are $\mod 2$.

First part of the question is to find an efficient randomized algorithm that finds an assignment to the variables over $\{0,1\}$ so that expected value of satisfied equations is $\frac{m}{2}$. This part is relatively easy, choosing a random assingment over $\{0,1\}$ gives us the desired result. Each equation is satisfied with probability $\frac{1}{2}$ and expected value over $m$ equations will give us $\frac{m}{2}$ satisfied equations.

The second part is the one I struggle with, it is asked to prove that there exist $O(logm)$ assignments to the variables such that every equation is satisfied by at least one assignment. And it is asked to propose a randomized efficient algorithm that finds those $O(logm)$ assignments with probability at least $\frac{1}{2}$. There is also a hint: let $E_i$ be an event that random assignment satisfies equation $i$, then events $E_i(1<=i<=m)$ are $2-wise$ independent.

I really don't know how to approach this. Any help would be appreciated.

Answer 1

You already proved in First part that using random assignments to the values it solves $\frac{m}{2}$ equations in expected value. Moreover, this fact came from knowing that each individual equation will be solved with probability $\frac{1}{2}$ on every random assignment. So we can use the following algorithm to solve this problem:

E = Unsolved equations (initially all equations)
A = {} # Assignments that solves the problem.

while E is not empty:
    a = Random assignment
    SE = solved_by(E, a) # Equations in E solved by assignment a
    if |SE| * 2 >= |E|:
         E = E \ SE      # Remove solved equations
         A = A U {a}     # Add this assignment to the solution

return A

This algorithm will find at most $\lfloor log_2(n) \rfloor + 1$ assignments so that every equation is solved by at least one assignment because condition if |SE| * 2 >= |E| half the size of |E| and add one assignment to A after every success. This will also run in time, since the probability of success is $\frac{1}{2}$, so the expected iterations for success is 2.