7 papers
Exact Label Recovery in Euclidean Random Graphs
Julia Gaudio, Charlie Guan, Xiaochun Niu +1
In this paper, we propose a family of label recovery problems on weighted Euclidean random graphs. The vertices of a graph are embedded in according to a Poisson poi…
An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
Julia Gaudio, Charlie K. Guan
Consider points generated uniformly at random in the unit square, and let be the length of their optimal traveling salesman tour. Beardwood, Halton, and Hammersley (1959)…
Exact Recovery in the Geometric Hidden Community Model
Julia Gaudio, Andrew Jin
Hidden community problems, such as community detection in the Stochastic Block Model (SBM), submatrix localization, and synchronization, have received considerable a…
Exact Recovery in the Geometric SBM
Julia Gaudio, Andrew Jin
Community detection is the problem of identifying dense communities in networks. Motivated by transitive behavior in social networks ("thy friend is my friend"), an emerging line o…
Semidefinite Programming for the Asymmetric Stochastic Block Model
Julia Gaudio, Phawin Prongpaophan
We consider semidefinite programming (SDP) for the binary stochastic block model with equal-sized communities. Prior work of Hajek, Wu, and Xu proposed an SDP (sym-SDP) for the sym…
Exact Community Recovery under Side Information: Optimality of Spectral Algorithms
Julia Gaudio, Nirmit Joshi
We study the problem of exact community recovery in general, two-community block models, in the presence of node-attributed . We allow for a very general side i…