Vấn đề cân bằng học tập với tiếng ồn (LPN) như sau
Để cho $\vec s\in\mathbb{F}_2^n$ là một bí mật cố định, và $\mathcal{O}_{\vec s}$ là một nhà tiên tri lấy mẫu $\vec a_i\gets \mathcal{U}(\mathbb{F}_2^n)$, $e_i \gets \mathsf{Bern}(\tau)$, và trả về $(\vec a_i, \langle \vec a_i, \vec s\rangle + e_i)$
Vấn đề LPN (tìm kiếm) là, được truy cập truy vấn vào oracle $\mathcal{O}_{\vec s}$, để lấy lại bí mật $\vec s$.
Nếu bạn hạn chế một số giới hạn truy vấn của $m$ về số lần bạn gọi $\mathcal{O}_{\vec s}$, vấn đề chính xác là vấn đề bạn đang quan tâm.
Khi tỷ lệ tiếng ồn $\tau$ là hằng số (là một hàm của $n$), iirc độ phức tạp nổi tiếng nhất để giải LPN là thuật toán Blum, Kalai, Wasserman (BKW), thuật toán này chạy theo thời gian, bộ nhớ và độ phức tạp của mẫu $2^{O(n/\log n)}$.
Vì vậy, chúng ta không nên (một cách tiệm cận) mong đợi sự phức tạp của nhiều thời gian.
Tuy nhiên, một cách cụ thể, đủ nhỏ $p$ tình hình là có thể xử lý được. Để đọc thêm về điều này, xem Giải mã LPN.
Tôi đã bao gồm một hình ảnh về thời gian chạy của các thuật toán LPN khác nhau bên dưới.
Đây, $\tau \in [0, 1/2]$ là "tỷ lệ nhiễu" và có thể được viết là $\tau = \min(p, 1-p)$ trong ký hiệu của bạn.
Lưu ý rằng đối với $p = 0,99$, chúng tôi có cái đó $\tau = 1/100$.
Sau đó, định lý 5 của bài báo được liên kết giải LPN với độ phức tạp thời gian/truy vấn
$$\tilde{\Theta}\left(\left(\frac{1}{(1-\tau)^n}\right)^{\frac{1}{1+\log\left(\frac{ 1}{1-\tau}\right)}}\right).$$
Điều này mang lại sự phức tạp về thời gian/truy vấn $\approx (100/99)^{\frac{n}{1+\log(100/99)}}$, mặc dù không phải là thời gian đa thức, nhưng sẽ khá hợp lý đối với kích thước vừa phải $n$.
