This course provides a detailed analysis of the Bethe Approximation for the Permanent. The learning outcomes include understanding the history, factors, and variations of the approximation method. Students will learn about better, beta, and bad approximations, as well as their distribution on perfect matchings and trees. The teaching method involves a theoretical approach with a focus on upper bounds. This course is intended for individuals interested in advanced topics in mathematics and theoretical computer science.
Overview
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
-
Distributed Lower Bounds for Ruling Sets
-
Network Coding Gaps for Completion Times of Multiple Unicasts
-
Tight Quantum Time-Space Tradeoffs for Function Inversion
-
Optimal Streaming Approximations for All Boolean Max 2-CSPs and Max k-SAT
-
Inapproximability of Clustering in Lp Metrics
-
Residual Based Sampling for Online Low Rank Approximation
