Image de couverture de livre

Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Chen, Tyler, Ray, Archan, Seshadri, Akshay, Herman, Dylan, Bach, Bao, Deshpande, Pranav, Som, Abhishek, Kumar, Niraj, Pistoia, Marco
Format:	Preprint
Publié:	2025
Sujets:	Quantum Physics Data Structures and Algorithms Machine Learning
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
par: Chen, Tyler, et autres
Publié: (2025)

A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
par: Chen, Tyler, et autres
Publié: (2025)

GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches
par: Chen, Tyler, et autres
Publié: (2025)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
par: Deák, Bence, et autres
Publié: (2026)

MetaTT: A Global Tensor-Train Adapter for Parameter-Efficient Fine-Tuning
par: Lopez-Piqueres, Javier, et autres
Publié: (2025)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
par: Arkhipov, Pavel, et autres
Publié: (2024)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
par: Fischer, David, et autres
Publié: (2022)

A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth
par: Kratsch, Stefan
Publié: (2026)

A faster algorithm for Vertex Cover parameterized by solution size
par: Harris, David G., et autres
Publié: (2022)

A faster algorithm for the construction of optimal factoring automata
par: Erlebach, Thomas, et autres
Publié: (2024)

An algebraic interpretation of Pauli flow, leading to faster flow-finding algorithms
par: Mitosek, Piotr, et autres
Publié: (2024)

On Speedups for Convex Optimization via Quantum Dynamics
par: Chakrabarti, Shouvanik, et autres
Publié: (2025)

The clustered Sparrow algorithm
par: Dumitrescu, Cristian
Publié: (2018)

Parameterized algorithms for $k$-Inversion
par: Antony, Dhanyamol, et autres
Publié: (2026)

Entropy Distribution as a Fingerprint for Hallucinations in Generative Models
par: Villani, Mattia J., et autres
Publié: (2026)

Counting perfect matchings and Hamiltonian cycles faster
par: Li, Baitian
Publié: (2023)

Insights into $(k,ρ)$-shortcutting algorithms
par: Leonhardt, Alexander, et autres
Publié: (2024)

Dynamic k-center clustering with lifetimes
par: Moretti, Simone, et autres
Publié: (2026)

Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization
par: Chakrabarti, Shouvanik, et autres
Publié: (2024)

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
par: Umans, Chris, et autres
Publié: (2025)

BalLOT: Balanced $k$-means clustering with optimal transport
par: Luo, Wenyan, et autres
Publié: (2025)

Local Search k-means++ with Foresight
par: Conrads, Theo, et autres
Publié: (2024)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
par: Censor-Hillel, Keren, et autres
Publié: (2025)

A faster algorithm for efficient longest common substring calculation for non-parametric entropy estimation in sequential data
par: Smart, Bridget, et autres
Publié: (2025)

The Lanczos algorithm for matrix functions: a handbook for scientists
par: Chen, Tyler
Publié: (2024)

Engineering faster double-array Aho-Corasick automata
par: Kanda, Shunsuke, et autres
Publié: (2022)

A faster heuristic for the Traveling Salesman Problem with Drone
par: Hokama, Pedro H. D. B., et autres
Publié: (2024)

Transference for loose Hamilton cycles in random 3‐uniform hypergraphs
par: Kalina Petrova, et autres
Publié: (2024)

Quantum Speedups for Derivative Pricing Beyond Black-Scholes
par: Herman, Dylan, et autres
Publié: (2026)

Adaptive and Robust Watermark for Generative Tabular Data
par: Ngo, Dung Daniel, et autres
Publié: (2024)

Faster algorithms for k-Orthogonal Vectors in low dimension
par: Dürr, Anita, et autres
Publié: (2025)

An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
par: Nutov, Zeev
Publié: (2022)

Fast $k$-means Seeding Under The Manifold Hypothesis
par: Shah, Poojan, et autres
Publié: (2026)

Dynamic algorithms for k-center on graphs
par: Cruciani, Emilio, et autres
Publié: (2023)

Provably Learning from Modern Language Models via Low Logit Rank
par: Golowich, Noah, et autres
Publié: (2025)

Round-efficient Fully-scalable MPC algorithms for k-Means
par: Jiang, Shaofeng H. -C., et autres
Publié: (2026)

A square root algorithm faster than Newton's method for multiprecision numbers, using floating-point arithmetic
par: Romano, Fabio
Publié: (2024)

Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs
par: Daga, Mohit
Publié: (2025)

A Faster $k$-means++ Algorithm
par: Liang, Jiehao, et autres
Publié: (2022)

A Simple PTAS for Weighted $k$-means and Sensor Coverage
par: Pareek, Akash, et autres
Publié: (2025)