Agreement Testing Theorems on Layered Set Systems
Offered By: IEEE via YouTube
Course Description
Overview
Explore agreement testing theorems on layered set systems in this 21-minute IEEE conference talk presented by Yotam Dikstein and Irit Dinur. Delve into a motivating example comparing lines versus LineGoldreich and Safra's general setup before examining the speakers' results. Discover where agreement tests arise in Constraint Satisfaction Problems (CSPs) and learn about 2-query CSP reduction. Investigate applications of agreement tests and review previous results in the field. Follow along with a rough sketch of the proof and consider open questions in this area of study. Gain valuable insights into this complex topic and its implications for computer science and mathematics.
Syllabus
Motivating Example Line vs. Line
Goldreich and Safra - General Setup
Our Results
Where do agreement tests arise in CSPs?
2 query CSP reduction
Applications of Agreement Tests
Previous Results
Proof Rough Sketch
Open Questions
The End
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube