Zobrazeno 1 - 10
of 143
pro vyhledávání: '"Bresler, Guy"'
We present a polynomial-time reduction from solving noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $\Theta(k\log n/\mathsf{poly}(\log k,\log q,\log\log n))$ with a uniformly random coefficient matrix to noisy linear equations over
Externí odkaz:
http://arxiv.org/abs/2411.12512
Autor:
Bangachev, Kiril, Bresler, Guy
The distribution $\mathsf{RGG}(n,\mathbb{S}^{d-1},p)$ is formed by sampling independent vectors $\{V_i\}_{i = 1}^n$ uniformly on $\mathbb{S}^{d-1}$ and placing an edge between pairs of vertices $i$ and $j$ for which $\langle V_i,V_j\rangle \ge \tau^p
Externí odkaz:
http://arxiv.org/abs/2408.00995
Autor:
Bangachev, Kiril, Bresler, Guy
The random geometric graph $\mathsf{RGG}(n,\mathbb{S}^{d-1}, p)$ is formed by sampling $n$ i.i.d. vectors $\{V_i\}_{i = 1}^n$ uniformly on $\mathbb{S}^{d-1}$ and placing an edge between pairs of vertices $i$ and $j$ for which $\langle V_i,V_j\rangle
Externí odkaz:
http://arxiv.org/abs/2402.12589
We study the problem of approximately transforming a sample from a source statistical model to a sample from a target statistical model without knowing the parameters of the source model, and construct several computationally efficient such reduction
Externí odkaz:
http://arxiv.org/abs/2402.07717
Autor:
Bangachev, Kiril, Bresler, Guy
In this paper we study the random geometric graph $\mathsf{RGG}(n,\mathbb{T}^d,\mathsf{Unif},\sigma^q_p,p)$ with $L_q$ distance where each vertex is sampled uniformly from the $d$-dimensional torus and where the connection radius is chosen so that th
Externí odkaz:
http://arxiv.org/abs/2310.14501
Autor:
Bresler, Guy, Jiang, Tianze
Planted Dense Subgraph (PDS) problem is a prototypical problem with a computational-statistical gap. It also exhibits an intriguing additional phenomenon: different tasks, such as detection or recovery, appear to have different computational limits.
Externí odkaz:
http://arxiv.org/abs/2306.17719
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles
We aim to understand the extent to which the noise distribution in a planted signal-plus-noise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient g
Externí odkaz:
http://arxiv.org/abs/2305.09995
Autor:
Bangachev, Kiril, Bresler, Guy
A random algebraic graph is defined by a group $G$ with a uniform distribution over it and a connection $\sigma:G\longrightarrow[0,1]$ with expectation $p,$ satisfying $\sigma(g)=\sigma(g^{-1}).$ The random graph $\mathsf{RAG}(n,G,p,\sigma)$ with ver
Externí odkaz:
http://arxiv.org/abs/2305.04802
In this paper we consider the problem of sampling from the low-temperature exponential random graph model (ERGM). The usual approach is via Markov chain Monte Carlo, but Bhamidi et al. showed that any local Markov chain suffers from an exponentially
Externí odkaz:
http://arxiv.org/abs/2208.13153
In the anisotropic random geometric graph model, vertices correspond to points drawn from a high-dimensional Gaussian distribution and two vertices are connected if their distance is smaller than a specified threshold. We study when it is possible to
Externí odkaz:
http://arxiv.org/abs/2206.14896