图 书 馆
理论计算机科学专题：概率可检查证明Topics In Theoretical Computer Science: Probabilistically Checkable Proofs |
|
| 课程网址: | https://ocw.mit.edu/courses/18-408-topics-in-theoretical-computer... |
| 主讲教师: | Prof. Dor Minzer |
| 开课单位: | 麻省理工学院 |
| 开课时间: | 2022-01-01 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | In this course, we will present the theory of Probabilistically Checkable Proofs (PCPs), and prove some fundamental consequences of it as well as more recent advances. More specifically, the first half of the course will be devoted to the (algebraic) proof of the basic PCP Theorem and basic relation to approximation problems. We will then move on to more advanced topics, such as hardness amplification, the long-code framework, the Unique-Games Conjecture and its implications, and the 2-to-2 Games Theorem.Show less |
| 关 键 词: | 概率可检查证明; 基本后果; 长代码框架 |
| 课程来源: | 麻省理工学院公开课 |
| 数据采集: | 2024-02-05：chenjy |
| 最后编审: | 2024-02-05：chenjy |
| 阅读次数: | 9 |