Buchumschlag

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Charikar, Moses, Compton, Spencer, Pabbaraju, Chirag
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Exploring Facets of Language Generation in the Limit
von: Charikar, Moses, et al.
Veröffentlicht: (2024)

Pareto-optimal Non-uniform Language Generation
von: Charikar, Moses, et al.
Veröffentlicht: (2025)

A Characterization of List Language Identification in the Limit
von: Charikar, Moses, et al.
Veröffentlicht: (2025)

Lower Bounds for Greedy Teaching Set Constructions
von: Compton, Spencer, et al.
Veröffentlicht: (2025)

New and Improved Bounds for Markov Paging
von: Pabbaraju, Chirag, et al.
Veröffentlicht: (2025)

A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses
von: Pabbaraju, Chirag, et al.
Veröffentlicht: (2025)

A Characterization of List Regression
von: Pabbaraju, Chirag, et al.
Veröffentlicht: (2024)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
von: Charikar, Moses, et al.
Veröffentlicht: (2024)

An Improved Greedy Approximation for (Metric) $k$-Means
von: Charikar, Moses, et al.
Veröffentlicht: (2026)

Dynamic Metric Embedding into $\ell_p$ Space
von: Banihashem, Kiarash, et al.
Veröffentlicht: (2024)

Learning with Monotone Adversarial Corruptions
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2026)

Testing with Non-identically Distributed Samples
von: Garg, Shivam, et al.
Veröffentlicht: (2023)

Efficient $\varepsilon$-approximate minimum-entropy couplings
von: Compton, Spencer
Veröffentlicht: (2025)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

Correlation Clustering Beyond the Pivot Algorithm
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Breaking the Metric Voting Distortion Barrier
von: Charikar, Moses, et al.
Veröffentlicht: (2023)

Additive Approximation Schemes for Low-Dimensional Embeddings
von: Anderson, Prashanti, et al.
Veröffentlicht: (2025)

Dynamic Data Layout Optimization with Worst-case Guarantees
von: Rong, Kexin, et al.
Veröffentlicht: (2024)

The Power of Recursive Embeddings for $\ell_p$ Metrics
von: Krauthgamer, Robert, et al.
Veröffentlicht: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
von: Brand, Jan van den, et al.
Veröffentlicht: (2026)

The Sample Complexity of Replicable Realizable PAC Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2026)

Approximately Dominating Sets in Elections
von: Charikar, Moses, et al.
Veröffentlicht: (2025)

Online Monotone Metric Embeddings
von: Coester, Christian, et al.
Veröffentlicht: (2026)

Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation
von: Compton, Spencer, et al.
Veröffentlicht: (2025)

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
von: Filtser, Arnold
Veröffentlicht: (2024)

Detecting Low-Degree Truncation
von: De, Anindya, et al.
Veröffentlicht: (2024)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
von: Makarychev, Yury, et al.
Veröffentlicht: (2024)

High-Accuracy List-Decodable Mean Estimation
von: Chen, Ziyun, et al.
Veröffentlicht: (2025)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
von: Kumar, Mithilesh, et al.
Veröffentlicht: (2016)

Exact Short Products From Truncated Multipliers
von: Lemire, Daniel
Veröffentlicht: (2023)

LZD-style Compression Scheme with Truncation and Repetitions
von: Götz, Linus, et al.
Veröffentlicht: (2025)

Efficient Parallel Ising Samplers via Localization Schemes
von: Chen, Xiaoyu, et al.
Veröffentlicht: (2025)

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
von: Bartal, Yair, et al.
Veröffentlicht: (2024)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2024)

Distributed Quantum Property Testing with Communication Constraints
von: Doosti, Mina, et al.
Veröffentlicht: (2026)

With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Design
von: Canonne, Clément L., et al.
Veröffentlicht: (2025)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
von: Bakshi, Ainesh, et al.
Veröffentlicht: (2023)

Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$
von: Chiclana, Rafael, et al.
Veröffentlicht: (2025)

On Finding $\ell$-th Smallest Perfect Matchings
von: Maalouly, Nicolas El, et al.
Veröffentlicht: (2025)