7 papers
A deterministic approximation for the permanent of a nonnegative matrix
Dingding Dong, Vishesh Jain
For every fixed , we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix , returns satisfy…
Optimal girth-dependent bounds for the Bethe approximation of the permanent
Dingding Dong, Vishesh Jain
For an nonnegative matrix , the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \[\operatorname{Bethe…
The Bethe-Hessian down to the Percolation Threshold
Dingding Dong, Theo McKenzie
The Bethe-Hessian is a symmetric matrix for which the negative spectrum has been observed to encode the informative structure of sparse stochastic block models. We prove that, in t…
Range of random -homomorphisms on weak expanders
Dingding Dong, Jinyoung Park
We prove that random -homomorphisms on weakly expanding bipartite graphs exhibit a strong "flatness" phenomenon. Extending prior work of Peled, Samotij, and Yehudayoff…
Even-degeneracy of a random graph
Ting-Wei Chao, Dingding Dong, Zixuan Xu
A graph is even-degenerate if one can iteratively remove a vertex of even degree at each step until at most one edge remains. Recently, Janzer and Yip showed that the Erdős--Renyi…
Arbitrary Spectral Edge of Regular Graphs
Dingding Dong, Theo McKenzie
We prove that for each and , the set of limit points of the first eigenvalues of sequences of -regular graphs is \[ \{(μ_1,\dots,μ_k): d=μ_1\geq \dots\geq…
Structure of tight (k,0)-stable graphs
Dingding Dong, Sammy Luo
We say that a graph G is -stable if removing vertices from it reduces its independence number by at most . We say that G is tight -stable if it is $(k…