From the 1 of 4 linked papers with an AI index.
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Derandomizing Matrix Concentration Inequalities from Free Probability
Robert Wang, Lap Chi Lau, Hong Zhou
Recently, sharp matrix concentration inequalities~\cite{BBvH23,BvH24} were developed using the theory of free probability. In this work, we design polynomial time deterministic alg…
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…