3 papers
cs.CC2023
Testing Junta Truncation
William He, Shivam Nadimpalli
We consider the basic statistical problem of detecting truncation of the uniform distribution on the Boolean hypercube by juntas. More concretely, we give upper and lower bounds on…
cs.DS2023
Beyond the Quadratic Time Barrier for Network Unreliability
Ruoxu Cen, William He, Jason Li +1
Karger (STOC 1995) gave the first FPTAS for the network (un)reliability problem, setting in motion research over the next three decades that obtained increasingly faster running ti…
cs.DS2022
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows
Ruoxu Cen, William He, Jason Li +1
We give an almost-linear time algorithm for the Steiner connectivity augmentation problem: given an undirected graph, find a smallest (or minimum weight) set of edges whose additio…