1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.