4 papers · 1 filter
Stable Algorithms Lower Bounds for Estimation
Xifan Yu, Ilias Zadik
In this work, we show that for all statistical estimation problems, a natural MMSE instability (discontinuity) condition implies the failure of stable algorithms, serving as a vers…
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…
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…
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…