Cover Image

Algorithms and Hardness for Estimating Statistical Similarity

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:	2025
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

Computational Explorations of Total Variation Distance
by: Bhattacharyya, Arnab, et al.
Published: (2024)

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

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)

Hardness and Algorithmic Results for Roman \{3\}-Domination
by: Reddy, Sangam Balchandar
Published: (2025)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
by: Gaikwad, Ajinkya, et al.
Published: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

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

Hardness of Dynamic Core and Truss Decompositions
by: Couto, Yan S., et al.
Published: (2025)

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

Improved Hardness-of-Approximation for Token Swapping
by: Hiken, Sam, et al.
Published: (2024)

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
by: Kleinberg, Robert, et al.
Published: (2026)

Sumplete is Hard, Even with Two Different Numbers
by: Ruangwises, Suthee
Published: (2023)

Hardness Results on Characteristics for Elastic-Degenerated Strings
by: Köppl, Dominik, et al.
Published: (2024)

Dequantization and Hardness of Spectral Sum Estimation
by: Edenhofer, Roman, et al.
Published: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
by: Gaikwad, Ajinkya, et al.
Published: (2026)

Testing Sumsets is Hard
by: Chen, Xi, et al.
Published: (2024)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
by: Curticapean, Radu, et al.
Published: (2024)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)

Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms
by: Antoniadis, Antonios, et al.
Published: (2025)

Deciding if a DAG is Interesting is Hard
by: De Carufel, Jean-Lou, et al.
Published: (2025)

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

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)

Improved Algorithm for Permutation Testing
by: Zhang, Xiaojin
Published: (2020)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

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

Parameterized Algorithms for Editing to Uniform Cluster Graph
by: Gaikwad, Ajinkya, et al.
Published: (2024)

From Amortized to Worst Case Delay in Enumeration Algorithms
by: Capelli, Florent, et al.
Published: (2021)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
by: Clinch, Katie, et al.
Published: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
by: Chmel, Petr, et al.
Published: (2026)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
by: Austrin, Per, et al.
Published: (2024)