Consider a constraint satisfaction problem $\mathbf{C}$ on finitely many independent random variables with dependency graph $G$. Let $p_a$ be the violation probability of a constraint $a\in \mathbf{C}$ and $N_G^2 (a)$ the set of constraints at distance one or two from $a$ in $G$. Suppose that, there exists $x\in (0,1)^...
Vishesh Jain, Clayton Mizgerd, H. Pham· 0 citations
For an $n\times n$ nonnegative matrix $A$, the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \[\operatorname{Bethe}(A) \leq \operatorname{per}(A) \leq 2^{n/2}\operatorname{Bethe}(A).\] The lower bound, due to Gurvits, is attained on forests. The upper bo...
We consider the problem of graphically local metric embedding, i.e. embedding points from an arbitrary finite metric space into a target metric space while preserving, up to a small distortion, only a subset of the pairwise distances specified by a bounded degree graph $G$. We provide a general reduction showing that,...
The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameter...
The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameter...
Vishesh Jain· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
