4 papers
Computational Thresholds for Balanced and Fixed-Slice Independent Sets in Bipartite Graphs
Ijay Narang, Will Perkins, Yuzhou Wang +1
Motivated by recent work of Kocurek, Oveis Gharan, and Tjowasi, which gives an efficient sampling algorithm for the hard-core model on random regular bipartite graphs by decomposin…
Constant-Stepsize Stochastic Approximation: Finite-Time Convergence, Gaussian Approximation, and Tail Bounds
Zedong Wang, Yuyang Wang, Ijay Narang +3
Constant-stepsize stochastic approximation (SA) is widely used in learning for computational efficiency, yet the distribution of the iterates is typically intractable. Classical as…
On the hardness of finding balanced independent sets in random bipartite graphs
Will Perkins, Yuzhou Wang
We consider the algorithmic problem of finding large \textit{balanced} independent sets in sparse random bipartite graphs, and more generally the problem of finding independent set…
Maximum determinant and permanent of sparse 0-1 matrices
Igor Araujo, József Balogh, Yuzhou Wang
We prove that the maximum determinant of an matrix, with entries in and at most non-zero entries, is at most , which is best possible when $k…