Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Quasi-Linear Size PCPs with Small Soundness from High-Dimensional Expanders

Institute for Advanced Study via YouTube

Overview

Explore a computer science seminar presentation that delves into groundbreaking research on Probabilistically Checkable Proofs (PCPs) and their optimization using high-dimensional expanders. Learn how to encode mathematical proofs in a format that allows verification through minimal queries, building upon Dinur's combinatorial proof of the PCP theorem. Discover the construction of 2-query, quasi-linear size PCPs with arbitrarily small constant soundness, and understand their implications for 3-SAT approximation algorithms under the exponential time hypothesis. Examine the fundamental components of PCPs, including encoding size and soundness parameters, while exploring the connection to recent developments in linear-size direct product testers with small soundness by various researchers. The presentation combines theoretical computer science with discrete mathematics, offering insights into proof verification systems that have significant applications in hardness of approximation, cryptography, and cloud computing.

Syllabus

Quasi-Linear Size PCPs with Small Soundness from High-Dimensional Expanders - Mitali Bafna

Taught by

Institute for Advanced Study

Reviews

Start your review of Quasi-Linear Size PCPs with Small Soundness from High-Dimensional Expanders

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.