Cover Image

Computational Explorations of Total Variation Distance

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhattacharyya, Arnab, Gayen, Sutanu, Meel, Kuldeep S., Myrisiotis, Dimitrios, Pavan, A., Vinodchandran, N. V.
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Total Variation Distance Meets Probabilistic Inference
by: Bhattacharyya, Arnab, et al.
Published: (2023)

Algorithms and Hardness for Estimating Statistical Similarity
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Distribution Learning Meets Graph Structure Sampling
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Learnability of Parameter-Bounded Bayes Nets
by: Bhattacharyya, Arnab, et al.
Published: (2024)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Exact Algorithms for Distance to Unique Vertex Cover
by: Fioravantes, Foivos, et al.
Published: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
by: Greilhuber, Jakob, et al.
Published: (2026)

Computational Complexity in Property Testing
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

The Structure of In-Place Space-Bounded Computation
by: Cook, James, et al.
Published: (2025)

Quadratic Speedup for Computing Contraction Fixed Points
by: Chen, Xi, et al.
Published: (2026)

Approximating the Total Variation Distance between Gaussians
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
by: John, Philips George, et al.
Published: (2024)

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
by: Kontogiannis, Andreas, et al.
Published: (2026)

Distance Estimation for High-Dimensional Discrete Distributions
by: Kumar, Gunjan, et al.
Published: (2023)

Approximate Algorithms for Chamfer Distance Under Translation
by: Halevi, Gil, et al.
Published: (2026)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
by: Bai, Tian, et al.
Published: (2026)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
by: Arvind, V., et al.
Published: (2023)

Computational Complexity of Swish
by: Horiyama, Takashi, et al.
Published: (2026)

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
by: Abu-Khzam, Faisal N., et al.
Published: (2024)

Quantum Channel Testing in Average-Case Distance
by: Rosenthal, Gregory, et al.
Published: (2024)

Distance Vector Domination
by: Cordasco, Gennaro, et al.
Published: (2024)

On the Maximum Distance Sublattice Problem and Closest Vector Problem
by: Kumar, Rajendra, et al.
Published: (2018)

Finding Minimum Distance Preservers: A Parameterized Study
by: Simonov, Kirill, et al.
Published: (2026)

Computing the $D$-base and $D$-relation in finite closure systems
by: Adaricheva, Kira, et al.
Published: (2024)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
by: Tate, Elise, et al.
Published: (2025)

Computational Complexities of Folding
by: Eppstein, David
Published: (2024)

Learning Functions of Halfspaces
by: Alman, Josh, et al.
Published: (2026)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

Detecting Low-Degree Truncation
by: De, Anindya, et al.
Published: (2024)

DNF formulas are efficiently testable with relative error
by: Chen, Xi, et al.
Published: (2026)

A Simple Proof that Ricochet Robots is PSPACE-Complete
by: Balanza-Martinez, Jose, et al.
Published: (2024)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
by: Frei, Fabian, et al.
Published: (2024)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

Testing noisy low-degree polynomials for sparsity
by: Bao, Yiqiao, et al.
Published: (2025)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
by: Frei, Fabian, et al.
Published: (2025)

Sublinear-query relative-error testing of halfspaces
by: Chen, Xi, et al.
Published: (2026)

Halfspaces are hard to test with relative error
by: Chen, Xi, et al.
Published: (2025)