Проблема четности обучения с шумом (LPN) выглядит следующим образом.
Позволять $\vec s\in\mathbb{F}_2^n$ быть фиксированным секретом, и $\mathcal{O}_{\vec s}$ быть оракулом, который пробует $\vec a_i\gets\mathcal{U}(\mathbb{F}_2^n)$, $e_i \gets\mathsf{Берн}(\tau)$, и возвращается $(\vec a_i, \langle \vec a_i, \vec s\rangle + e_i)$
Проблема (поиска) LPN заключается в том, что при наличии запроса на доступ к оракулу $\mathcal{O}_{\vec s}$, чтобы восстановить секрет $\vec с$.
Если вы ограничите некоторую границу запроса $м$ сколько раз ты звонишь $\mathcal{O}_{\vec s}$, это именно та проблема, которая вас интересует.
Когда уровень шума $\тау$ постоянна (как функция $n$), iirc самая известная сложность для решения LPN - это алгоритм Блюма, Калаи, Вассермана (BKW), который работает во времени, памяти и сложности выборки. $2^{O(n/\log n)}$.
Таким образом, мы не должны (асимптотически) ожидать поливременной сложности.
Конкретно, однако, для достаточно малых $р$ ситуация разрешима. Для получения дополнительной информации об этом см. LPN декодировано.
Я включил изображение времени работы различных алгоритмов LPN ниже.
Здесь, $\тау \in [0, 1/2]$ является «коэффициентом шума» и может быть записан как $\тау = \мин(р, 1-р)$ в вашей нотации.
Обратите внимание, что для $р = 0,99$, у нас есть это $\тау = 1/100$.
Тогда теорема 5 из связанной статьи решает LPN со сложностью времени/запроса.
$$\tilde{\Theta}\left(\left(\frac{1}{(1-\tau)^n}\right)^{\frac{1}{1+\log\left(\frac{ 1}{1-\тау}\право)}}\право).$$
Это дает сложность времени/запроса $ \ приблизительно (100/99) ^ {\ гидроразрыва {n} {1+ \ log (100/99)}} $, что, хотя и не является полиномиальным, должно быть вполне разумным для среднего размера $n$.
