Copertina

Additive Approximation Schemes for Low-Dimensional Embeddings

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Anderson, Prashanti, Bakshi, Ainesh, Hopkins, Samuel B.
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding
di: Anderson, Prashanti, et al.
Pubblicazione: (2026)

Sample-Optimal Private Regression in Polynomial Time
di: Anderson, Prashanti, et al.
Pubblicazione: (2025)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
di: Bakshi, Ainesh, et al.
Pubblicazione: (2023)

Faster MAX-CUT on Bounded Threshold Rank Graphs
di: Anderson, Prashanti, et al.
Pubblicazione: (2025)

An Improved Classical Singular Value Transformation for Quantum Machine Learning
di: Bakshi, Ainesh, et al.
Pubblicazione: (2023)

Rapid mixing for high-temperature Gibbs states with arbitrary external fields
di: Bakshi, Ainesh, et al.
Pubblicazione: (2026)

A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature
di: Bakshi, Ainesh, et al.
Pubblicazione: (2025)

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
di: Bakshi, Ainesh, et al.
Pubblicazione: (2026)

Efficient Certificates of Anti-Concentration Beyond Gaussians
di: Bakshi, Ainesh, et al.
Pubblicazione: (2024)

Structure learning of Hamiltonians from real-time evolution
di: Bakshi, Ainesh, et al.
Pubblicazione: (2024)

Learning quantum Hamiltonians at any temperature in polynomial time
di: Bakshi, Ainesh, et al.
Pubblicazione: (2023)

High-Temperature Gibbs States are Unentangled and Efficiently Preparable
di: Bakshi, Ainesh, et al.
Pubblicazione: (2024)

An Additive Approximation Scheme for Generating Dyadic Codings for the Outputs of an LLM
di: Bar-Lev, Daniella, et al.
Pubblicazione: (2026)

Improved Additive Approximation Algorithms for APSP
di: Jin, Ce, et al.
Pubblicazione: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
di: Neuwohner, Meike, et al.
Pubblicazione: (2025)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
di: Roditty, Liam, et al.
Pubblicazione: (2025)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
di: Kar, Debajyoti, et al.
Pubblicazione: (2026)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
di: Bentert, Matthias, et al.
Pubblicazione: (2025)

Clustering under Constraints: Efficient Parameterized Approximation Schemes
di: Bhore, Sujoy, et al.
Pubblicazione: (2025)

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
di: Ren, Kinter, et al.
Pubblicazione: (2024)

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics
di: Charikar, Moses, et al.
Pubblicazione: (2023)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
di: Mao, Xiao, et al.
Pubblicazione: (2026)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
di: Driemel, Anne, et al.
Pubblicazione: (2026)

Improved Approximation Algorithms for Three-Dimensional Knapsack
di: Jansen, Klaus, et al.
Pubblicazione: (2025)

Consistent Low-Rank Approximation
di: Woodruff, David P., et al.
Pubblicazione: (2026)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
di: Manurangsi, Pasin
Pubblicazione: (2024)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
di: Mömke, Tobias, et al.
Pubblicazione: (2024)

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

Differentially Private High-Dimensional Approximate Range Counting, Revisited
di: Aumüller, Martin, et al.
Pubblicazione: (2024)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2026)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
di: Cervenjak, Philip, et al.
Pubblicazione: (2024)

Kd-tree Based Wasserstein Distance Approximation for High-Dimensional Data
di: Teshigawara, Kanata, et al.
Pubblicazione: (2026)

Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion
di: McCauley, Samuel
Pubblicazione: (2024)

A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
di: Saller, Sophia, et al.
Pubblicazione: (2023)

Approximation Schemes for Sequential Hiring Problems
di: Segev, Danny, et al.
Pubblicazione: (2026)

Faster Algorithms for Schatten-p Low Rank Approximation
di: Kacham, Praneeth, et al.
Pubblicazione: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
di: Chitnis, Rajesh, et al.
Pubblicazione: (2024)

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
di: Kyng, Rasmus, et al.
Pubblicazione: (2025)