# Finding efficient randomized algorithm

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.

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.