A Tight Analysis of Bethe Approximation for Permanent
Offered By: IEEE via YouTube
Course Description
Overview
Explore a rigorous analysis of the Bethe approximation for permanent in this 23-minute IEEE conference talk. Delve into the problem, its approximation history, and various approximation factors. Learn about better approximation techniques, including the Beta approximation, and understand the distribution on perfect matchings and trees. Examine upper bounds and gain insights into both good and bad approximation methods. Presented by Nima Anari and Alireza Rezaei, this talk provides a comprehensive overview of the topic, from introduction to summary.
Syllabus
Introduction
The Problem
Approximation History
Approximation Factors
Better Approximation
Beta Approximation
Bad Approximation
Distribution on Perfect Matchings
Distribution on Trees
Upper Bounds
Summary
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