Copertina

Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bhattacharyya, Arnab, Gayen, Sutanu, Meel, Kuldeep S., Myrisiotis, Dimitrios, Pavan, A., Vinodchandran, N. V.
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
di: Fortnow, Lance
Pubblicazione: (2025)

Probabilistic Explanations for Linear Models
di: Subercaseaux, Bernardo, et al.
Pubblicazione: (2024)

Total Search Problems in $\mathsf{ZPP}$
di: Fleming, Noah, et al.
Pubblicazione: (2025)

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
di: Zschetzsche, Lilith, et al.
Pubblicazione: (2026)

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

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
di: Nalli, Sai Soumya, et al.
Pubblicazione: (2026)

Counting and Sampling Traces in Regular Languages
di: de Colnet, Alexis, et al.
Pubblicazione: (2025)

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
di: Grier, Daniel, et al.
Pubblicazione: (2026)

Towards a universal gateset for $\mathsf{QMA}_1$
di: Rudolph, Dorian
Pubblicazione: (2024)

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$
di: Chen, Lijie, et al.
Pubblicazione: (2024)

Learning High-dimensional Gaussians from Censored Data
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2025)

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
di: Liu, Yuxi
Pubblicazione: (2025)

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
di: Hsieh, Min-Hsiu, et al.
Pubblicazione: (2024)

The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
di: Göller, Stefan, et al.
Pubblicazione: (2023)

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
di: Rudolph, Dorian, et al.
Pubblicazione: (2024)

Wataridori is NP-Complete
di: Ruangwises, Suthee
Pubblicazione: (2026)

Nondango is NP-Complete
di: Ruangwises, Suthee
Pubblicazione: (2023)

Extensively Not P-Bi-Immune promiseBQP-Complete Languages
di: Jackson, Andrew
Pubblicazione: (2024)

Normality criterion for a family of holomorphic curves that partially share wandering hyperplanes with their derivatives, and holomorphic functions lifted to curves in $P^2(\mathbb{C})$
di: Mehta, Sonam, et al.
Pubblicazione: (2024)

Communication Complexity of Disjointness under Product Distributions
di: Hunter, Zach, et al.
Pubblicazione: (2026)

NP-Completeness of Neighborhood Balanced Colorings
di: Asaeedi, Saeed
Pubblicazione: (2024)

Affine Rank Minimization is ER Complete
di: Majumdar, Angshul
Pubblicazione: (2026)

The 2-Attractor Problem is NP-Complete
di: Fuchs, Janosch, et al.
Pubblicazione: (2023)

Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers
di: Li, Xiaoyu, et al.
Pubblicazione: (2024)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
di: Morimae, Tomoyuki, et al.
Pubblicazione: (2025)

No Complete Problem for Constant-Cost Randomized Communication
di: Fang, Yuting, et al.
Pubblicazione: (2024)

NP-Completeness of Multicast Beamforming in Wireless Communication
di: Shrestha, Sagar
Pubblicazione: (2025)

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
di: Cao, Yang, et al.
Pubblicazione: (2024)

Constant-Cost Communication is not Reducible to k-Hamming Distance
di: Fang, Yuting, et al.
Pubblicazione: (2024)

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
di: Minevich, Igor, et al.
Pubblicazione: (2024)

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
di: Casteigts, Arnaud, et al.
Pubblicazione: (2024)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
di: Bhattiprolu, Vijay, et al.
Pubblicazione: (2025)

Flat origami is Turing Complete
di: Hull, Thomas C., et al.
Pubblicazione: (2023)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
di: Amireddy, Prashanth, et al.
Pubblicazione: (2025)

Characterizing the Distinguishability of Product Distributions through Multicalibration
di: Marcussen, Cassandra, et al.
Pubblicazione: (2024)