Yuzhou Wang

Yuzhou Wang

Publications

On the hardness of finding balanced independent sets in random bipartite graphs

Published in SODA 2024, 2024

We give evidence of a statistical-computational gap for finding balanced independent sets in random bipartite graphs of average degree d, where d is a large constant. While balanced independent sets of density (2+o_d(1)) log d/d exist whp in such graphs, ther best known efficient algorithm (which is very simple) can only find balanced independent sets of half this size. We show that neither local algorithms nor low-degree algorithms can do better.

Recommended citation: Perkins, Will, and Yuzhou Wang. "On the hardness of finding balanced independent sets in random bipartite graphs." arXiv preprint arXiv:2307.13921 (2023). https://arxiv.org/abs/2307.13921

Maximum determinant and permanent of sparse 0-1 matrices

Published in Linear Algebra and its Applications, 2022

We prove that the maximum determinant of an n by n matrix, with entries in {0,1} and at most n+k non-zero entries, is at most 2^{k/3}, which is best possible when k is a multiple of 3.

Recommended citation: Araujo, Igor, József Balogh, and Yuzhou Wang. "Maximum determinant and permanent of sparse 0-1 matrices." Linear Algebra and its Applications 645 (2022): 194-228. https://www.sciencedirect.com/science/article/abs/pii/S0024379522001215?via%3Dihub