Explanipedia

Finding Planted Cycles in a Random Graph Open

Julia Gaudio, Colin Sandon, Jiaming Xu, Dana Yang · 2025

In this paper, we study the problem of finding a collection of planted cycles in an \ER random graph $G \sim \mathcal{G}(n, λ/n)$, in analogy to the famous Planted Clique Problem. When the cycles are planted on a uniformly random subset of…

Sharp exact recovery threshold for two-community Euclidean random graphs Open

Julia Gaudio, C. Y. Guan · 2025

This paper considers the problem of label recovery in random graphs and matrices. Motivated by transitive behavior in real-world networks (i.e., ``the friend of my friend is my friend''), a recent line of work considers spatially-embedded …

Exact Label Recovery in Euclidean Random Graphs Open

Julia Gaudio, C. Y. Guan, Xiaochun Niu, Ermin Wei · 2024

In this paper, we propose a family of label recovery problems on weighted Euclidean random graphs. The vertices of a graph are embedded in $\mathbb{R}^d$ according to a Poisson point process, and are assigned to a discrete community label.…

Exact Community Recovery under Side Information: Optimality of Spectral Algorithms Open

Julia Gaudio, Nirmit Joshi · 2024

We study the problem of exact community recovery in general, two-community block models, in the presence of node-attributed $side$ $information$. We allow for a very general side information channel for node attributes, and for pairwise (e…

The Power of Two Matrices in Spectral Algorithms for Community Recovery Open

Souvik Dhara, Julia Gaudio, Elchanan Mossel, Colin Sandon · 2023

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spe…

Exact Community Recovery in the Geometric SBM Open

Julia Gaudio, Xiaochun Niu, Ermin Wei · 2023

We study the problem of exact community recovery in the Geometric Stochastic Block Model (GSBM), where each vertex has an unknown community label as well as a known position, generated according to a Poisson point process in $\mathbb{R}^d$…

Average-case and smoothed analysis of graph isomorphism Open

Julia Gaudio, Miklós Z. Rácz, Anirudh Sridhar · 2022

We propose a simple and efficient local algorithm for graph isomorphism which succeeds for a large class of sparse graphs. This algorithm produces a low-depth canonical labeling, which is a labeling of the vertices of the graph that identi…

Joint Facility and Demand Location Problem Open

Ali Kaan Kurbanzade, Julia Gaudio · 2022

In typical applications of facility location problems, the location of demand is assumed to be an input to the problem. The demand may be fixed or dynamic, but ultimately outside the optimizers control. In contrast, there are settings, esp…

The Power of Two Matrices in Spectral Algorithms for Community Recovery Open

Souvik Dhara, Julia Gaudio, Elchanan Mossel, Colin Sandon · 2022

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spe…

Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix Open

Julia Gaudio, Nirmit Joshi · 2022

Community detection is a fundamental problem in network science. In this paper, we consider community detection in hypergraphs drawn from the $hypergraph$ $stochastic$ $block$ $model$ (HSBM), with a focus on exact community recovery. We st…

Exact Community Recovery in Correlated Stochastic Block Models Open

Julia Gaudio, Miklós Z. Rácz, Anirudh Sridhar · 2022

We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmi…

Spectral Algorithms Optimally Recover Planted Sub-structures Open

Souvik Dhara, Julia Gaudio, Elchanan Mossel, Colin Sandon · 2022

Spectral algorithms are an important building block in machine learning and graph algorithms. We are interested in studying when such algorithms can be applied directly to provide optimal solutions to inference tasks. Previous works by Abb…

Shotgun assembly of Erdős-Rényi random graphs Open

Julia Gaudio, Elchanan Mossel · 2022

Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of \ER random graphs $G(n, p_n)$, where $p_n = n^{-α}$ for $0 < α< 1$. We consider…

Spectral recovery of binary censored block models Open

Souvik Dhara, Julia Gaudio, Elchanan Mossel, Colin Sandon · 2022

Community detection is the problem of identifying community structure in graphs. Often the graph is modeled as a sample from the Stochastic Block Model, in which each vertex belongs to a community. The probability that two vertices are con…

Shotgun Assembly of Erd\H{o}s-R\'enyi Random Graphs Open

Julia Gaudio, Elchanan Mossel · 2020

Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of Erd\H{o}s-R\'enyi random graphs $G(n, p_n)$, where $p_n = n^{-\alpha}$ for $0 <…

A large deviation principle for block models Open

Christian Borgs, Jennifer Chayes, Julia Gaudio, Samantha Petti, Subhabrata Sen · 2020

We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee-Varadhan(2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we stud…

Estimation of Monotone Multi-Index Models Open

David Gamarnik, Julia Gaudio · 2020

In a multi-index model with $k$ index vectors, the input variables are transformed by taking inner products with the index vectors. A transfer function $f: \mathbb{R}^k \to \mathbb{R}$ is applied to these inner products to generate the out…

Attracting random walks Open

Julia Gaudio, Yury Polyanskiy · 2020

This paper introduces the Attracting Random Walks model, which describes the dynamics of a system of particles on a graph with $n$ vertices. At each step, a single particle moves to an adjacent vertex (or stays at the current one) with pro…

An improved lower bound for the Traveling Salesman constant Open

Julia Gaudio, Patrick Jaillet · 2019

Sparse High-Dimensional Isotonic Regression Open

David Gamarnik, Julia Gaudio · 2019

We consider the problem of estimating an unknown coordinate-wise monotone function given noisy measurements, known as the isotonic regression problem. Often, only a small subset of the features affects the output. This motivates the sparse…

Sparse High-Dimensional Isotonic Regression Open

David Gamarnik, Julia Gaudio · 2019

© 2019 Neural information processing systems foundation. All rights reserved. We consider the problem of estimating an unknown coordinate-wise monotone function given noisy measurements, known as the isotonic regression problem. Often, onl…

Exponential Convergence Rates for Stochastically Ordered Markov Processes with Random Initial Conditions Open

Julia Gaudio, Saurabh Amin, Patrick Jaillet · 2018

In this brief paper we find computable exponential convergence rates for a large class of stochastically ordered Markov processes. We extend the result of Lund, Meyn, and Tweedie (1996), who found exponential convergence rates for stochast…

Exponential Convergence Rates for Stochastically Ordered Markov\n Processes with Random Initial Conditions Open

Julia Gaudio, Saurabh Amin, Patrick Jaillet · 2018

In this brief paper we find computable exponential convergence rates for a\nlarge class of stochastically ordered Markov processes. We extend the result of\nLund, Meyn, and Tweedie (1996), who found exponential convergence rates for\nstoch…

Julia Gaudio YOU? Author Swipe