Showing 2024Show all
3 papers · 1 filter
cs.DS2024
Streaming and Communication Complexity of Load-Balancing via Matching Contractors
Sepehr Assadi, Aaron Bernstein, Zachary Langley +2
In the load-balancing problem, we have an -vertex bipartite graph between a set of clients and servers. The goal is to find an assignment of all clients to the ser…
cs.DS2024
Experimental Design Using Interlacing Polynomials
Lap Chi Lau, Robert Wang, Hong Zhou
We present a unified deterministic approach for experimental design problems using the method of interlacing polynomials. Our framework recovers the best-known approximation guaran…
cs.DS2024
Spectral Sparsification by Deterministic Discrepancy Walk
Lap Chi Lau, Robert Wang, Hong Zhou
Spectral sparsification and discrepancy minimization are two well-studied areas that are closely related. Building on recent connections between these two areas, we generalize the…