17 citations · 19 across the 17 of their papers we have counts for
20 papers · 1 filter
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…
On the Houdré-Tetali conjecture about an isoperimetric constant of graphs
Lap Chi Lau, Dante Tjowasi
Houdré and Tetali defined a class of isoperimetric constants of graphs for , and conjectured a Cheeger-type inequality for of the form $$λ_2 \les…
Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues
Lap Chi Lau, Kam Chuen Tung, Robert Wang
We consider a new semidefinite programming relaxation for directed edge expansion, which is obtained by adding triangle inequalities to the reweighted eigenvalue formulation. Apply…
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…
Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues
Lap Chi Lau, Kam Chuen Tung, Robert Wang
We derive Cheeger inequalities for directed graphs and hypergraphs using the reweighted eigenvalue approach that was recently developed for vertex expansion in undirected graphs [O…