Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRapid mixing from spectral independence beyond the Boolean domain
229
0
0.0
(
0
)
Added by
Weiming Feng
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper $q$-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree $Delta$ provided $qge (alpha^*+delta)Delta$ where $alpha^*approx 1.763$ is the unique solution to $alpha^*=exp(1/alpha^*)$ and $delta>0$ is any constant. This is the first efficient algorithm for sampling proper $q$-colourings in this regime with possibly unbounded $Delta$. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].
rate research
Read More
We prove an optimal $Omega(n^{-1})$ lower bound on the spectral gap of Glauber dynamics for anti-ferromagnetic two-spin systems with $n$ vertices in the tree uniqueness regime. This spectral gap holds for all, including unbounded, maximum degree $Delta$. Consequently, we have the following mixing time bounds for the models satisfying the uniqueness condition with a slack $deltain(0,1)$: $bullet$ $C(delta) n^2log n$ mixing time for the hardcore model with fugacity $lambdale (1-delta)lambda_c(Delta)= (1-delta)frac{(Delta - 1)^{Delta - 1}}{(Delta - 2)^Delta}$; $bullet$ $C(delta) n^2$ mixing time for the Ising model with edge activity $betainleft[frac{Delta-2+delta}{Delta-delta},frac{Delta-delta}{Delta-2+delta}right]$; where the maximum degree $Delta$ may depend on the number of vertices $n$, and $C(delta)$ depends only on $delta$. Our proof is built upon the recently developed connections between the Glauber dynamics for spin systems and the high-dimensional expander walks. In particular, we prove a stronger notion of spectral independence, called the complete spectral independence, and use a novel Markov chain called the field dynamics to connect this stronger spectral independence to the rapid mixing of Glauber dynamics for all degrees.
We present a new lower bound on the spectral gap of the Glauber dynamics for the Gibbs distribution of a spectrally independent $q$-spin system on a graph $G = (V,E)$ with maximum degree $Delta$. Notably, for several interesting examples, our bound covers the entire regime of $Delta$ excluded by arguments based on coupling with the stationary distribution. As concrete applications, by combining our new lower bound with known spectral independence computations and known coupling arguments: (1) We show that for a triangle-free graph $G = (V,E)$ with maximum degree $Delta geq 3$, the Glauber dynamics for the uniform distribution on proper $k$-colorings with $k geq (1.763dots + delta)Delta$ colors has spectral gap $tilde{Omega}_{delta}(|V|^{-1})$. Previously, such a result was known either if the girth of $G$ is at least $5$ [Dyer et.~al, FOCS 2004], or under restrictions on $Delta$ [Chen et.~al, STOC 2021; Hayes-Vigoda, FOCS 2003]. (2) We show that for a regular graph $G = (V,E)$ with degree $Delta geq 3$ and girth at least $6$, and for any $varepsilon, delta > 0$, the partition function of the hardcore model with fugacity $lambda leq (1-delta)lambda_{c}(Delta)$ may be approximated within a $(1+varepsilon)$-multiplicative factor in time $tilde{O}_{delta}(n^{2}varepsilon^{-2})$. Previously, such a result was known if the girth is at least $7$ [Efthymiou et.~al, SICOMP 2019]. (3) We show for the binomial random graph $G(n,d/n)$ with $d = O(1)$, with high probability, an approximately uniformly random matching may be sampled in time $O_{d}(n^{2+o(1)})$. This improves the corresponding running time of $tilde{O}_{d}(n^{3})$ due to [Jerrum-Sinclair, SICOMP 1989; Jerrum, 2003].
We introduce a family of quantum semigroups and their natural coactions on noncommutative polynomials. We present three invariance conditions, associated with these coactions, for the joint distribution of sequences of selfadjoint noncommutative random variables. For one of the invariance conditions, we prove that the joint distribution of an infinite sequence of noncommutative random variables satisfies it is equivalent to the fact that the sequence of the random variables are identically distributed and boolean independent with respect to the conditional expectation onto its tail algebra. This is a boolean analogue of de Finetti theorem on exchangeable sequences. In the end of the paper, we will discuss the other two invariance conditions which lead to some trivial results.
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $kleq log n$, and an error parameter $epsilon > 0$, our algorithm runs in space $tilde{O}(klog (Ncdot w_{mathrm{max}}/w_{mathrm{min}}))$ where $w_{mathrm{max}}$ and $w_{mathrm{min}}$ are the maximum and minimum edge weights in $G$, and produces a weighted graph $H$ with $tilde{O}(n^{1+2/k}/epsilon^2)$ edges that spectrally approximates $G$, in the sense of Spielmen and Teng [ST04], up to an error of $epsilon$. Our algorithm is based on a new bounded-independence analysis of Spielman and Srivastavas effective resistance based edge sampling algorithm [SS08] and uses results from recent work on space-bounded Laplacian solvers [MRSV17]. In particular, we demonstrate an inherent tradeoff (via upper and lower bounds) between the amount of (bounded) independence used in the edge sampling algorithm, denoted by $k$ above, and the resulting sparsity that can be achieved.
In this paper, we develop the notion of free-Boolean independence in an amalgamation setting. We construct free-Boolean cumulants and show that the vanishing of mixed free-Boolean cumulants is equivalent to our free-Boolean independence with amalgamation. We also provide a characterization of free-Boolean independence by conditions in terms of mixed moments. In addition, we study free-Boolean independence over a $C^*$-algebra and prove a positivity property.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
