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

YouTube

Efficient PCPs from HDX

International Centre for Theoretical Sciences via YouTube

Overview

Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
Explore the construction of efficient Probabilistically Checkable Proofs (PCPs) using High Dimensional Expanders (HDX) in this 37-minute conference talk. Learn how HDX structures can be leveraged to create more efficient PCP constructions, examining the theoretical foundations and practical implications of this approach. Discover the connections between high-dimensional expansion properties and proof verification systems, understanding how the geometric and algebraic properties of HDX contribute to improved efficiency in probabilistic proof checking. Gain insights into the mathematical techniques used to analyze these constructions and their potential applications in computational complexity theory. Understand the role of expansion properties in simplicial complexes and hypergraphs as they relate to proof systems, exploring how these higher-dimensional structures provide advantages over traditional graph-based approaches in PCP construction.

Syllabus

Efficient PCPs from HDX  by Mitali Bafna

Taught by

International Centre for Theoretical Sciences

Reviews

Start your review of Efficient PCPs from HDX

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.