8 papers
The Hypergraph Moore Bound
Afonso S. Bandeira, Dmitriy Kunisky, Petar Nizić-Nikolac +2
The hypergraph Moore bound conjectured by Feige (2008) controls the size of the smallest even cover in a -uniform hypergraph in terms of the average density of hyperedges. An ev…
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…
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…
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…
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…