YoVDO

Smoothing the Gap Between NP and ER

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Algorithms Courses Theoretical Computer Science Courses Standard Model Courses Complexity Theory Courses

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

Information Theory
The Chinese University of Hong Kong via Coursera
Intro to Computer Science
University of Virginia via Udacity
Analytic Combinatorics, Part I
Princeton University via Coursera
Algorithms, Part I
Princeton University via Coursera
Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera