[Proof Complexity] MIAO seminar Fri Jan 19 at 14:00 CET with Arnab Bhattacharyya: TV distance estimation is as easy as probabilistic inference

[Jakob Nordström]

Dear all,

On Friday January 19 at 14:00 CET we will have the pleasure of listening to Arnab Bhattacharyya from the National University of Singapore, who will give a talk titled "TV distance estimation is as easy as probabilistic inference". You find the abstract at the bottom of this message.

This will be a video seminar at https://lu-se.zoom.us/j/61925271827. Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at http://jakobnordstrom.se/miao-seminars/ . In particular, our plans for January are as follows:
- Friday Jan 12 at 14:00: Proving UNSAT in zero knowledge (Ning Luo, Northwestern University)
- Monday Jan 15 at 14:00: The planted clique conjecture holds for unary Sherali-Adams (Kilian Risse, EPFL)
- Friday Jan 19 at 14:00: TV distance estimation is as easy as probabilistic inference (Arnab Bhattacharyya, National University of Singapore)
- Monday Jan 29 at 16:00 (note the time!): Fourier growth of communication protocols for XOR functions (Uma Girish, Princeton University)

If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

P.S. Apologies for any multiple copies you might receive of this announcement --- our seminar mailing list is not feeling very well right now.

**********

Friday Jan 19 at 14:00 on Zoom
TV distance estimation is as easy as probabilistic inference
(Arnab Bhattacharyya, National University of Singapore)

We discuss the algorithmic problem of computing the total variation (TV) distance between two high-dimensional probability distributions. Two highlights are:

1. The problem of exactly computing the TV distance between two product distributions is #P-complete. This is in stark contrast with other distance measures such as KL, Chi-square, and Hellinger which tensorize over the marginals leading to efficient algorithms.

2. We show a novel connection between TV distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for estimating TV distances between distributions that are defined by Bayes nets of bounded treewidth. Our approach employs a new notion of partial couplings of high-dimensional distributions, which might be of independent interest.

Joint work with Sutanu Gayen (IIT Kanpur), Kuldeep Meel (Toronto & NUS), Dimitrios Myrisiotis (NUS), A. Pavan (Iowa State), and N.V. Vinodchandran (U. Nebraska Lincoln).


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98 / +45 28 78 38 11
https://jakobnordstrom.se