3 papers
cs.DS2026
On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths
Yu Cheng, Tianle Jiang, Pachara Sawettamalya +1
We revisit several fundamental graph problems in the deterministic two-party communication model. Our main contributions include: (1) a new -bit protocol fo…
cs.DS2026
On the Cost of Non-Adaptivity in Matroid Prophet Inequalities
Tianle Jiang
Matroid prophet inequalities admit an optimal 2-competitive algorithm, which relies on adaptively updating thresholds based on previous outcomes. Motivated by applications to poste…
cs.LG2026
Simple KNN-Based Outlier Detection Achieves Robust Clustering
Tianle Jiang, Yufa Zhou
Being robust to the presence of outliers is crucial for applying clustering algorithms in practice. In the $\textit{robust $k$-Means}$ problem (i.e., -Means with outliers), the…