15 papers
Fundamental Limits of Query-Based Subgraph Detection
Wasim Huleihel
The planted subgraph detection problem asks whether a random graph contains a hidden structured subgraph. In the classical formulation, the entire adjacency matrix is observed and…
Recovery of Planted Subgraphs
Wasim Huleihel
Understanding the fundamental limits of recovering planted subgraphs in random graphs is a central challenge in high-dimensional statistics and theoretical computer science. While…
Robust Detection of Planted Subgraphs in Semi-Random Models
Dor Elimelech, Wasim Huleihel
Detection of planted subgraphs in Erdös-Rényi random graphs has been extensively studied, leading to a rich body of results characterizing both statistical and computational thre…
Testing for a Hidden Geometry in Random Graphs
Amit Silber, Mor Oren-Loberman, Wasim Huleihel
We study the problem of detecting a faint geometric signal hidden in an otherwise random graph. Formally, we consider a hypothesis testing problem in which, under the null, the obs…
Inhomogeneous Submatrix Detection
Mor Oren-Loberman, Dvir Jerbi, Tamir Bendory +1
In this paper, we study the problem of detecting multiple hidden submatrices in a large Gaussian random matrix when the planted signal is inhomogeneous across entries. Under the nu…
Einstein from Noise: Statistical Analysis
Amnon Balanov, Wasim Huleihel, Tamir Bendory
``Einstein from noise" (EfN) is a prominent example of the model bias phenomenon: systematic errors in the statistical model that lead to spurious but consistent estimates. In the…