Buchumschlag

Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Basu, Debabrota, Chanda, Debarshi
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Machine Learning Computers and Society Data Structures and Algorithms Computation
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Continuous Fairness On Data Streams
von: Ghosh, Subhodeep, et al.
Veröffentlicht: (2026)

A Scalable Algorithm for Individually Fair K-means Clustering
von: Bateni, MohammadHossein, et al.
Veröffentlicht: (2024)

Fair Submodular Cover
von: Chen, Wenjing, et al.
Veröffentlicht: (2024)

Time Fairness in Online Knapsack Problems
von: Lechowicz, Adam, et al.
Veröffentlicht: (2023)

Causal Equal Protection as Algorithmic Fairness
von: Di Bello, Marcello, et al.
Veröffentlicht: (2024)

Fairness Implications of Encoding Protected Categorical Attributes
von: Mougan, Carlos, et al.
Veröffentlicht: (2022)

Fairness in Streaming Submodular Maximization over a Matroid Constraint
von: Halabi, Marwa El, et al.
Veröffentlicht: (2023)

Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size
von: Chanda, Debarshi
Veröffentlicht: (2025)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
von: Bishnu, Arijit, et al.
Veröffentlicht: (2025)

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
von: Funk, Nicole, et al.
Veröffentlicht: (2026)

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
von: Zhu, Yanhui, et al.
Veröffentlicht: (2024)

Terminal Embeddings in Sublinear Time
von: Cherapanamjeri, Yeshwanth, et al.
Veröffentlicht: (2021)

Total Variation Distance Meets Probabilistic Inference
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2023)

Fair Clustering: Critique, Caveats, and Future Directions
von: Dickerson, John, et al.
Veröffentlicht: (2024)

Robust Fair Clustering with Group Membership Uncertainty Sets
von: Duppala, Sharmila, et al.
Veröffentlicht: (2024)

Correcting Underrepresentation and Intersectional Bias for Classification
von: Diana, Emily, et al.
Veröffentlicht: (2023)

Matchings, Predictions and Counterfactual Harm in Refugee Resettlement Processes
von: Lee, Seungeon, et al.
Veröffentlicht: (2024)

Scalable Algorithms for Individual Preference Stable Clustering
von: Mosenzon, Ron, et al.
Veröffentlicht: (2024)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
von: Hu, Hang, et al.
Veröffentlicht: (2022)

Generalizing Fair Top-$k$ Selection: An Integrative Approach
von: Cai, Guangya
Veröffentlicht: (2026)

Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
von: Blum, Avrim, et al.
Veröffentlicht: (2025)

Approximating the Total Variation Distance between Gaussians
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

Balanced Spanning Tree Distributions Have Separation Fairness
von: Chen, Harry, et al.
Veröffentlicht: (2025)

Computational Explorations of Total Variation Distance
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2024)

On Computing Total Variation Distance Between Mixtures of Product Distributions
von: Feng, Weiming, et al.
Veröffentlicht: (2026)

Sublinear Time Quantum Algorithm for Attention Approximation
von: Song, Zhao, et al.
Veröffentlicht: (2026)

Dynamic Correlation Clustering in Sublinear Update Time
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Training Overparametrized Neural Networks in Sublinear Time
von: Deng, Yichuan, et al.
Veröffentlicht: (2022)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)

Fast-MWEM: Private Data Release in Sublinear Time
von: Haris, Themistoklis, et al.
Veröffentlicht: (2026)

Welfare-Centric Clustering
von: Zhang, Claire Jie, et al.
Veröffentlicht: (2025)

Verifying Classification with Limited Disclosure
von: Bhandari, Siddharth, et al.
Veröffentlicht: (2025)

Centralized Selection with Preferences in the Presence of Biases
von: Celis, L. Elisa, et al.
Veröffentlicht: (2024)

Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model
von: Feng, Weiming, et al.
Veröffentlicht: (2025)

Private Synthetic Graph Generation and Fused Gromov-Wasserstein Distance
von: Wirth, Leoni Carla, et al.
Veröffentlicht: (2025)

Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling
von: Zhou, Felix
Veröffentlicht: (2025)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
von: Danait, Ved, et al.
Veröffentlicht: (2025)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
von: Greenhut, Daniel, et al.
Veröffentlicht: (2025)

The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions
von: McWhorter, Atticus, et al.
Veröffentlicht: (2025)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
von: Biedl, Therese, et al.
Veröffentlicht: (2026)