Trouver un algorithme randomisé efficace

Question

Je fais un cours sur les algorithmes randomisés et j'ai rencontré une question que j'ai du mal à résoudre.

Compte tenu d'un système de $ m $ équations linéaires avec $ n $ Variables sur un champ fini $ mathbb {f_2} $ où chaque équation est de forme $ a_1x_1 + ... + a_nx_n = b mod 2 $ et $ x_i, a_i, b in {0,1 } $ et la multiplication et la somme sont $ mod 2 $.

Première partie de la question est de trouver un algorithme randomisé efficace qui trouve une affectation aux variables sur $\{0,1\}$ de sorte que la valeur attendue des équations satisfaites est $ frac {m} {2} $. Cette partie est relativement facile, en choisissant un assassin aléatoire $\{0,1\}$ nous donne le résultat souhaité. Chaque équation est satisfaite de la probabilité $ frac {1} {2} $ et la valeur attendue sur $ m $ Les équations nous donneront $ frac {m} {2} $ équations satisfaites.

La seconde partie est celui avec lequel je lutte, on demande de prouver qu'il existe $ O (logm) $ affectations aux variables telles que chaque équation est satisfaite par au moins une affectation. Et il est demandé de proposer un algorithme efficace randomisé qui trouve ces $ O (logm) $ affectations avec probabilité au moins $ frac {1} {2} $. Il y a aussi un indice: laisser $ E_i $ être un événement que l'attribution aléatoire satisfait à l'équation $ i $, puis événements $ E_i (1 <= i <= m) $ sommes 2 $ à 2 $ indépendant.

Je ne sais vraiment pas comment aborder cela. Toute aide serait appréciée.