Learning Parity with Noise|| @ CMU || Lecture 26b of CS Theory Toolkit

Learning Parity with Noise|| @ CMU || Lecture 26b of CS Theory Toolkit

by Ryan O'Donnell

Formal & Physical Sciences AI — Models & Research UYQArtificial intelligence (AI)UYQMMachine learning
🎙 Ryan O'Donnell 👥 14K 📅 July 15, 2020 ⏱ 11 min 👁 2K 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

LPNlearning parity with noisecryptographyhardness assumptionGaussian elimination

Summary

This lecture, part of a graduate course on theoretical computer science at Carnegie Mellon, introduces the Learning Parity with Noise (LPN) problem, a fundamental hardness assumption in cryptography. The instructor, Ryan O’Donnell, begins by contextualizing LPN within the broader landscape of cryptographic assumptions, contrasting it with one-way functions and the Learning With Errors (LWE) problem. He explains that LPN is essentially LWE over the field of size 2, making it simpler but with fewer known applications. The lecture formally defines the LPN problem: given access to noisy linear equations over GF(2) involving a secret vector, the goal is to recover the secret. The noise rate is a constant epsilon. The instructor emphasizes that despite its simplicity, no polynomial-time algorithm is known for constant noise rates, even small ones. He then discusses the implications of LPN, noting that it implies the existence of one-way functions and thus symmetric-key encryption, but it is unclear if it suffices for public-key encryption. The lecture also covers the fastest known algorithms for LPN, including the Blum-Kalai-Wasserman (BKW) algorithm, which runs in time 2^(n/log n), and a variant that uses fewer samples but runs in 2^(n/log log n). The instructor also touches on the concept of indistinguishability obfuscation (iO) as a stronger assumption, but does not delve into details. The lecture concludes by suggesting that LPN is a relatively safe assumption for cryptographic purposes.

228 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a clear and rigorous introduction to the LPN problem, situating it within the broader context of cryptographic hardness assumptions. The argumentation is solid: the instructor explains the problem definition, its relationship to LWE, and its implications for cryptography. He also discusses the state-of-the-art algorithms, giving a balanced view of the assumption’s strength. The value lies in its pedagogical clarity and the expert perspective on the current research landscape.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, delivered by an expert in the field. The content is accurate and up-to-date, reflecting the current understanding of LPN. The title accurately describes the content. The sources cited are limited to the instructor’s personal page and course homepage, which are appropriate for a lecture. The lecture does not provide a formal bibliography, but it references key works such as the BKW algorithm and the work of Alekhnovich on public-key encryption from LPN.

163 words

Title / Content Match

The title accurately reflects the content: the lecture focuses on the Learning Parity with Noise (LPN) problem, presented as part of a CS Theory Toolkit course.

Quality & Reliability

8/10

Lecture by a recognized expert in theoretical computer science, part of a graduate course at Carnegie Mellon. The content is technically accurate and well-structured, but it is a lecture without formal peer review or citations to primary sources.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

  • Ryan O'Donnell's homepage — Instructor's academic page, providing credentials and related materials.
  • Course homepage on Diderot — Course page for CS Theory Toolkit, containing lecture notes and resources.
  • Rebecca Kiger Photography — Photographer credited for the thumbnail image.

Concurring Sources

  • Learning with errors — Wikipedia article on LWE, which is closely related to LPN and supports the lecture's claims.
  • LPN problem — Wikipedia article on LPN, providing background and algorithmic details.

Contribution & Novelties

The lecture provides a concise and accessible introduction to the LPN problem, which is a fundamental hardness assumption in cryptography. It clarifies the relationship between LPN and LWE, and discusses the state-of-the-art algorithms, making it a valuable resource for students and researchers. The lecture also touches on the broader landscape of cryptographic assumptions, including iO, providing context for LPN’s role.

Pour aller plus loin :

  • Learning with errors — Wikipedia article on LWE, the generalization of LPN.
  • Blum-Kalai-Wasserman algorithm — Wikipedia article on LPN, including the BKW algorithm.
  • Indistinguishability obfuscation — Wikipedia article on iO, a related but stronger assumption.

100 words

Radar Profile

The radar profile shows high scores in quality, technical level, and reliability, with a slightly lower score for quantity of information due to the lecture's brevity. This indicates a focused, expert-level presentation with strong content but limited breadth.

Reliability 8/10