ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Open Problem. It remains an open problem to relate the canonical path method to the spectral independence technique. Sampling Bases of Matroids: Given a matroid M of rank n, defined on the ground set of elements U , let \pin be the uniform distribution over the bases of M . In [3] it was shown that such a distribution is 2-spectrally independent therefore the down-up walk gives a fast algorithm to sample bases of matroids. As a consequence this work gave the first efficient algo- rithm to sample forests of a given graph or to sample from the “reliability polynomial” of matroids. Sampling from the Hard-core Distribution: Given a graph G = (V, E) with n vertices, a set S \subseteq V is an independent set if there are no edges of E connecting vertices of S. Define U to be the set of (v, in), (v, out) for any v \in V . Given an “activity threshold” \lambda > 0, let \pin be the distribution over Un where a set S \in Un is in the support of \pin if every vertex is either in or out and the set of in vertices form an independent set of G. In such a case we define \pin (S) = \lambda#in vertices . This probability distribution is called the hard-core model and it is of utmost importance in statistical physiscs to design efficient algorithm to sample from \pin for the largest possible value of \lambda. In sequence of works [2, 5] it was shown for

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.