YoVDO

Concentration on HDX: Derandomization Beyond Chernoff - Lecture

Offered By: Institute for Advanced Study via YouTube

Tags

Theoretical Computer Science Courses Graph Theory Courses Complexity Theory Courses Probability Theory Courses Derandomization Courses Concentration Inequalities Courses High Dimensional Expanders Courses

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore a cutting-edge computer science and discrete mathematics seminar on concentration bounds and derandomization techniques. Delve into the evolution of Chernoff's bound, from the Expander-Chernoff Theorem to high-dimensional expanders (HDX). Examine the limitations of expander walks for higher degree functions and discover how HDX offer a solution for achieving stronger concentration results. Investigate the implications of these advancements for agreement testing, probabilistically checkable proofs (PCPs), and reverse hypercontractivity. Learn about the latest research closing the gap between HDX and complete hypergraph concentration bounds, presented by Max Hopkins from the Institute for Advanced Study.

Syllabus

Concentration on HDX: Derandomization Beyond Chernoff - Max Hopkins


Taught by

Institute for Advanced Study

Related Courses

Randomized Methods in Complexity
Indian Institute of Technology Kanpur via Swayam
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen
Institute for Advanced Study via YouTube
Expander Graph Application 2: Derandomization - Lecture 16c of CS Theory Toolkit
Ryan O'Donnell via YouTube
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Association for Computing Machinery (ACM) via YouTube
High-Precision Estimation of Random Walks in Small Space
IEEE via YouTube