Showing math.STShow all
3 papers · 1 filter
math.ST2024
Statistical inference of a ranked community in a directed graph
Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein +1
We study the problem of detecting or recovering a planted ranked subgraph from a directed graph, an analog for directed graphs of the well-studied planted dense subgraph model. We…
math.ST2024
Inference of rankings planted in random tournaments
Dmitriy Kunisky, Daniel A. Spielman, Xifan Yu
We consider the problem of inferring an unknown ranking of items from a random tournament on vertices whose edge directions are correlated with the ranking. We establish, i…
math.ST2024
Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
Xifan Yu, Ilias Zadik, Peiyuan Zhang
We study the computational limits of the following general hypothesis testing problem. Let H=H_n be an \emph{arbitrary} undirected graph on n vertices. We study the detection task…