3 papers
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.DS2025
A Combinatorial Characterization of Constant Mixing Time
Lap Chi Lau, Raymond Liu
Classical spectral graph theory characterizes graphs with logarithmic mixing time. In this work, we present a combinatorial characterization of graphs with constant mixing time. Th…
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…