Approximating the TV Distance Between Two Product Distributions

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=gZHGI3EOzLk


Duration: 43:54
986 views
15

Weiming Feng (University of Edinburgh)
https://simons.berkeley.edu/talks/weiming-feng-university-edinburgh-2023-10-20
Probabilistic Circuits and Logic

The total variation (TV) distance is a fundamental metric to measure the difference between two distributions. Recently, Bhattacharyya et al. initiated the problem of computing the TV distance between two high-dimensional distributions. They proved that the exact computing of TV distance, even for product distributions over the Boolean domain, is #P-hard.

In this talk, I will discuss some recent progress in approximating the TV distance between two product distributions. I will introduce a randomized approximation algorithm based on the coupling technique and a deterministic algorithm based on the sparsification of distributions.



Other Videos By Simons Institute for the Theory of Computing


2023-10-27Simple Proofs of Important Results in Market Design
2023-10-27Stable Matching by Optimal Transport
2023-10-27Revealed Preferences of One-Sided Matching
2023-10-27Strict Core Stability and Strategy-Proofness for Hedonic Games with Friend-Oriented Preferences
2023-10-27Market Design for Priority-Based Assignment with Distributional Objectives
2023-10-27Estimating Separable Matching Models
2023-10-27The Intractability of Hylland-Zeckhauser and its Aftermath
2023-10-27Endogenous Market Formation: Theory and Evidence from Chilean College Admissions
2023-10-26Algorithmic Mechanism Design with Investment
2023-10-20Utilizing Structure in Combinatorial Solving and Reasoning
2023-10-20Approximating the TV Distance Between Two Product Distributions
2023-10-20Tractable Control for Autoregressive Language Generation
2023-10-20On Finding Modes of Gaussian Sum-Product Networks
2023-10-20Marginal Determinism in Structured Decomposable Circuits
2023-10-19Weighted Model Integration
2023-10-19An Approximate Skolem Function Counter
2023-10-19Subtractive Mixture Models: Representation and Learning
2023-10-19The Rise of Tractable Circuits: From Cryptography to Continuous Generative Models
2023-10-19Decision Diagrams for Efficient Inference and Optimization in Expressive Discrete+Continuous Domains
2023-10-18Solving Marginal MAP Exactly by Probabilistic Circuit Transformations
2023-10-18Direct Access for Conjunctive Queries with Negation


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Probabilistic Circuits and Logic
Weiming Feng