О пороге отношения аппроксимации для реоптимизации задачи о максимальном количестве выполненных уравнений в линейных системах над конечным полем - Михайлюк, В.А. (Кибернетика и системный анализ, 2012)
При вставленні довільного рівняння в лінійну систему над полем GF(2), кожне рівняння якої містить рівно три змінні з множини від n змінних, задача про максимальне число виконаних рівнянь реоптимізована з відношенням апроксимації 3/2. Показано, що це відношення апроксимації є пороговим. Подібний результат виконується для систем, кожне рівняння яких містить k змінних при k = O (log n).