Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Commutativity in the Algorithmic Lovasz Local Lemma   We consider the recent formulation of the Algorithmic Lov\'asz Local Lemma
[10,2,3] for finding objects that avoid `bad features', or `flaws'. It extends
the Moser-Tardos resampling algorithm [17] to more general discrete spaces. At
each step the method picks a flaw present in the current state and goes to a
new state according to some prespecified probability distribution (which
depends on the current state and the selected flaw). However, it is less
flexible than the Moser-Tardos method since [10,2,3] require a specific flaw
selection rule, whereas [17] allows an arbitrary rule (and thus can potentially
be implemented more efficiently).
  We formulate a new "commutativity" condition, and prove that it is sufficient
for an arbitrary rule to work. It also enables an efficient parallelization
under an additional assumption. We then show that existing resampling oracles
for perfect matchings and permutations do satisfy this condition.

12
The categories of this paper are: nucl-th
8
The categories of this paper are: hep-ex
13
The categories of this paper are: quant-ph
37
The categories of this paper are: supr-con
11
The categories of this paper are: hep-lat
6
The categories of this paper are: astro-ph
10
The categories of this paper are: q-bio
34
The categories of this paper are: chem-ph
23
The categories of this paper are: solv-int
9
The categories of this paper are: nlin
27
The categories of this paper are: comp-gas
22
The categories of this paper are: chao-dyn
24
The categories of this paper are: dg-ga
18
The categories of this paper are: econ
16
The categories of this paper are: stat
2
The categories of this paper are: math