Responsible AI for Social Empowerment and Education (RAISE)
Responsible AI for Social Empowerment and Education (RAISE)
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.
Duration: Not defined
Level: Undergraduate
Certification: No
Cost: Free
Language: English
Type: Self-Paced
Please note: these courses are provided by external sources, links are not actively managed or regularly updated, content might be moved or unavailable.
