Вопрос

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.

Нет правильного решения

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top