Witness-tree probability conjecture for fully orderable witness trees
Witness-tree probability conjecture for fully orderable witness trees
A witness tree is built from bad-event labels, with children of a node labeled required to have distinct labels whose set is orderable to . For a tree-structure , let P(\text{\tau appears}) denote the probability that it appears, and let be the corresponding witness-tree weight. Witness-tree lemma conjecture. If this orderability condition is enforced at every node of , then
The paper explains that this would strengthen the analysis of the Swapping Algorithm by controlling witness trees at every node rather than only at the root. Establishing the bound requires fine control over the temporal order of resamplings, which the authors were unable to maintain; the conjecture is presented as an open extension of their witness-tree lemma.
Sources & referencesView supporting material
Primary source
David G. Harris, “New bounds for the Moser-Tardos distribution”, arXiv:1610.09653 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.