Smoothing the Gap Between NP and ER
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 23-minute IEEE conference talk that delves into smoothing techniques to bridge the gap between NP and ER problems. Join Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow as they present their research on applying smooth analysis to computational geometry problems. Learn about the standard model, the rationale behind smooth analysis, and its effectiveness in tackling complex computational challenges. Discover key results and their implications for ER-complete problems and recognition problems, with a practical example to illustrate the concepts discussed.
Syllabus
Intro
Detour
Standard model
Smooth Analysis
Why does it work
First result
Second result
ER complete problems
Recognition problems
Example
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