On Approximating Total Variation Distance
Authors: Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we introduce and study the problem of computing the TV distance of two product distributions over the domain {0, 1}n. In particular, we establish the following results. 1. The problem of exactly computing the TV distance of two product distributions is #P-complete. ... 2. There is a fully polynomial-time deterministic approximation scheme (FPTAS) for computing the TV distance of two product distributions P and Q where Q is the uniform distribution. ... The present work makes significant progress towards this research goal. |
| Researcher Affiliation | Academia | 1National University of Singapore 2Indian Institute of Technology Kanpur 3Iowa State University 4University of Nebraska-Lincoln |
| Pseudocode | No | The paper describes algorithmic ideas and reductions but does not present them in a structured pseudocode or algorithm block format. |
| Open Source Code | No | The paper does not include any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper focused on complexity theory and algorithms; it does not utilize or refer to publicly available datasets in the context of empirical evaluation. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experiments with training, validation, and test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments that would require specific hardware for execution. |
| Software Dependencies | No | The paper is theoretical and does not specify software dependencies with version numbers for running algorithms or experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |