Approximating Profile Maximum Likelihood Efficiently - New Bounds on the Bethe Permanent by Moses Charikar

Explore a seminar on approximating profile maximum likelihood efficiently and new bounds on the Bethe permanent. Delve into symmetric properties of distributions and their estimators, focusing on the universal plug-in estimator that maximizes profile maximum likelihood (PML). Learn about the first polynomial-time computable PML estimator with a 2^{n^{1-delta}}-approximation guarantee, computable in nearly linear time. Discover the connection between the introduced convex relaxation and the Bethe free energy approximation, leading to new bounds on the Bethe permanent of non-negative matrices. Gain insights from speaker Moses Charikar of Stanford University as he covers topics including setup, sequence maximum likelihood, fixed distribution P, universal estimators, open questions, and new results.

Introduction
Setup
Profile Maximum Likelihood
Sequence Maximum Likelihood
Fixed Distribution P
How the two connected
Universal estimator
Two questions
Open question
Recap
New Result
Theorem
Conclusion