7 papers · 1 filter
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…
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…
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…
Experimental Design for Any -Norm
Lap Chi Lau, Robert Wang, Hong Zhou
We consider a general -norm objective for experimental design problems that captures some well-studied objectives (D/A/E-design) as special cases. We prove that a randomized loc…
A Local Search Framework for Experimental Design
Lap Chi Lau, Hong Zhou
We present a local search framework to design and analyze both combinatorial algorithms and rounding algorithms for experimental design problems. This framework provides a unifying…
A Spectral Approach to Network Design
Lap Chi Lau, Hong Zhou
We present a spectral approach to design approximation algorithms for network design problems. We observe that the underlying mathematical questions are the spectral rounding probl…
Network design for s-t effective resistance
Pak Hay Chan, Lap Chi Lau, Aaron Schild +2
We consider a new problem of designing a network with small - effective resistance. In this problem, we are given an undirected graph , two designated vertices $s,t…