Zobrazeno 1 - 10
of 94
pro vyhledávání: '"Wein, Alexander S."'
Many problems in high-dimensional statistics appear to have a statistical-computational gap: a range of values of the signal-to-noise ratio where inference is information-theoretically possible, but (conjecturally) computationally intractable. A cano
Externí odkaz:
http://arxiv.org/abs/2404.18735
We consider the problem of detecting a planted clique of size $k$ in a random graph on $n$ vertices. When the size of the clique exceeds $\Theta(\sqrt{n})$, polynomial-time algorithms for detection proliferate. We study faster -- namely, sublinear ti
Externí odkaz:
http://arxiv.org/abs/2402.05451
We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. In this model, a dense cycle of expected bandwidth $n \tau$, representing the hidden one-dimensional geometry of vertices, is planted in an
Externí odkaz:
http://arxiv.org/abs/2402.00305
The Metropolis process (MP) and Simulated Annealing (SA) are stochastic local search heuristics that are often used in solving combinatorial optimization problems. Despite significant interest, there are very few theoretical results regarding the qua
Externí odkaz:
http://arxiv.org/abs/2312.13554
Autor:
Moitra, Ankur, Wein, Alexander S.
We revisit the fundamental question of simple-versus-simple hypothesis testing with an eye towards computational complexity, as the statistically optimal likelihood ratio test is often computationally intractable in high-dimensional settings. In the
Externí odkaz:
http://arxiv.org/abs/2311.00289
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem that has been extensively studied in recent years. We study a hypergraph version of the problem. Let $G^r(n,p)$ denote the $r$-uniform Erd\
Externí odkaz:
http://arxiv.org/abs/2304.08135
We study the computational complexity of two related problems: recovering a planted $q$-coloring in $G(n,1/2)$, and finding efficiently verifiable witnesses of non-$q$-colorability (a.k.a. refutations) in $G(n,1/2)$. Our main results show hardness fo
Externí odkaz:
http://arxiv.org/abs/2303.00252
Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biology. We consider a model where a dense cycle with expected bandwidth $n
Externí odkaz:
http://arxiv.org/abs/2302.06737
Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerg
Externí odkaz:
http://arxiv.org/abs/2212.10872
Autor:
Montanari, Andrea, Wein, Alexander S.
We consider the problem of estimating an unknown parameter vector ${\boldsymbol \theta}\in{\mathbb R}^n$, given noisy observations ${\boldsymbol Y} = {\boldsymbol \theta}{\boldsymbol \theta}^{\top}/\sqrt{n}+{\boldsymbol Z}$ of the rank-one matrix ${\
Externí odkaz:
http://arxiv.org/abs/2212.06996