Cover Image

A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Tyler, Seshadri, Akshay, Villani, Mattia J., Niroula, Pradeep, Chakrabarti, Shouvanik, Ray, Archan, Deshpande, Pranav, Yalovetzky, Romina, Pistoia, Marco, Kumar, Niraj
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling
by: Chen, Tyler, et al.
Published: (2025)

GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches
by: Chen, Tyler, et al.
Published: (2025)

A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
by: Chen, Tyler, et al.
Published: (2025)

Entropy Distribution as a Fingerprint for Hallucinations in Generative Models
by: Villani, Mattia J., et al.
Published: (2026)

Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization
by: Chakrabarti, Shouvanik, et al.
Published: (2024)

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
by: Chowdhury, Agniva, et al.
Published: (2024)

On Speedups for Convex Optimization via Quantum Dynamics
by: Chakrabarti, Shouvanik, et al.
Published: (2025)

Quantum Speedups for Derivative Pricing Beyond Black-Scholes
by: Herman, Dylan, et al.
Published: (2026)

QC-Forest: a Classical-Quantum Algorithm to Provably Speedup Retraining of Random Forest
by: Yalovetzky, Romina, et al.
Published: (2024)

Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited
by: Mehlhorn, Kurt, et al.
Published: (2026)

MetaTT: A Global Tensor-Train Adapter for Parameter-Efficient Fine-Tuning
by: Lopez-Piqueres, Javier, et al.
Published: (2025)

Efficient Data Shapley for Weighted Nearest Neighbor Algorithms
by: Wang, Jiachen T., et al.
Published: (2024)

Efficient and Provable Algorithms for Covariate Shift
by: Adil, Deeksha, et al.
Published: (2025)

Finding missing items requires strong forms of randomness
by: Chakrabarti, Amit, et al.
Published: (2023)

Wagner's Algorithm Provably Runs in Subexponential Time for SIS$^\infty$
by: Ducas, Léo, et al.
Published: (2025)

Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms
by: White, Nathan, et al.
Published: (2026)

SVD Provably Denoises Nearest Neighbor Data
by: Kannan, Ravindran, et al.
Published: (2026)

Provably Fast and Space-Efficient Parallel Biconnectivity
by: Dong, Xiaojun, et al.
Published: (2023)

A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
by: Derakhshan, Mahsa, et al.
Published: (2026)

Quantum Speedups for Group Relaxations of Integer Linear Programs
by: Augustino, Brandon, et al.
Published: (2026)

AutoCSF: Provably Space-Efficient Indexing of Skewed Key-Value Workloads via Filter-Augmented Compressed Static Functions
by: Ramos, David Torres, et al.
Published: (2026)

Simple and Optimal Sublinear Algorithms for Mean Estimation
by: Bertolotti, Beatrice, et al.
Published: (2024)

Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams
by: Chakrabarti, Amit, et al.
Published: (2024)

Vantage Point Selection Algorithms for Bottleneck Capacity Estimation
by: Ashvinkumar, Vikrant, et al.
Published: (2025)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
by: Peng, Pan, et al.
Published: (2025)

UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees
by: De Man, Quinten, et al.
Published: (2026)

Non-Splitting Coflow Scheduling with Provable Guarantees in Heterogeneous Parallel Networks
by: Chen, Chi-Yeh
Published: (2025)

Mechanisms for Quantum Advantage in Global Optimization of Nonconvex Functions
by: Herman, Dylan, et al.
Published: (2025)

A Tight Competitive Ratio for Online Submodular Welfare Maximization
by: Ganz, Amit, et al.
Published: (2023)

Balanced Learned Sort: a new learned model for fast and balanced item bucketing
by: Ferragina, Paolo, et al.
Published: (2024)

Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size
by: Chanda, Debarshi
Published: (2025)

Scalable and Provable Kemeny Constant Computation on Static and Dynamic Graphs: A 2-Forest Sampling Approach
by: Li, Cheng, et al.
Published: (2025)

Provable Quantization with Randomized Hadamard Transform
by: Feng, Ying, et al.
Published: (2026)

Dynamic Spectral Clustering with Provable Approximation Guarantee
by: Laenen, Steinar, et al.
Published: (2024)

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

Sequential Diversification with Provable Guarantees
by: Wang, Honglian, et al.
Published: (2024)

A Unified and Scalable Algorithm Framework of User-Defined Temporal $(k,\mathcal{X})$-Core Query
by: Zhong, Ming, et al.
Published: (2023)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
by: Hayderi, Alexandre, et al.
Published: (2024)

Provably learning a multi-head attention layer
by: Chen, Sitan, et al.
Published: (2024)

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
by: Im, Sungjin, et al.
Published: (2025)