First optimal algorithm for fair top-k aggregation and 2-approximation for fair full rank aggregation under Spearman footrule (L1 distance).
Journal of the ACM (JACM) , volume=
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
years
2026 4verdicts
UNVERDICTED 4representative citing papers
LAPRAS uses predictions to answer likely queries with the offline Matrix Mechanism and paces residual budget for unpredicted queries via unbiased stopping-time estimation from the first few unexpected arrivals, achieving near-offline utility when overlap is high.
An efficient algorithm recovers phylogenetic trees from Θ(n) noisy quartets under random classification noise, matching the information-theoretic lower bound and achieving near-optimal quartet distance.
Triplet constraints realizable in D-dimensional Euclidean space cannot be preserved above 50% accuracy by any embedding of dimension at most cD for constant c<1, with UGC-hardness preventing better polynomial-time solutions in any dimension.
citing papers explorer
-
Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking
First optimal algorithm for fair top-k aggregation and 2-approximation for fair full rank aggregation under Spearman footrule (L1 distance).
-
LAPRAS : Learning-Augmented PRivate Answering for linear query Streams
LAPRAS uses predictions to answer likely queries with the offline Matrix Mechanism and paces residual budget for unpredicted queries via unbiased stopping-time estimation from the first few unexpected arrivals, achieving near-offline utility when overlap is high.
-
Optimal Phylogenetic Reconstruction from Sampled Quartets
An efficient algorithm recovers phylogenetic trees from Θ(n) noisy quartets under random classification noise, matching the information-theoretic lower bound and achieving near-optimal quartet distance.
-
Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
Triplet constraints realizable in D-dimensional Euclidean space cannot be preserved above 50% accuracy by any embedding of dimension at most cD for constant c<1, with UGC-hardness preventing better polynomial-time solutions in any dimension.