3 papers
cs.DS2024
Sample-Based Matroid Prophet Inequalities
Hu Fu, Pinyan Lu, Zhihao Gavin Tang +3
We study matroid prophet inequalities when distributions are unknown and accessible only through samples. While single-sample prophet inequalities for special matroids are known, n…
cs.DS2024
A Faster Algorithm for Pigeonhole Equal Sums
Ce Jin, Hongxun Wu
An important area of research in exact algorithms is to solve Subset-Sum-type problems faster than meet-in-middle. In this paper we study Pigeonhole Equal Sums, a total search prob…
cs.LG2024
The Cost of Parallelizing Boosting
Xin Lyu, Hongxun Wu, Junzhao Yang
We study the cost of parallelizing weak-to-strong boosting algorithms for learning, following the recent work of Karbasi and Larsen. Our main results are two-fold: - First, we prov…