Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Evidence for Long-Tails in SLS Algorithms   Stochastic local search (SLS) is a successful paradigm for solving the
satisfiability problem of propositional logic. A recent development in this
area involves solving not the original instance, but a modified, yet logically
equivalent one. Empirically, this technique was found to be promising as it
improves the performance of state-of-the-art SLS solvers.
  Currently, there is only a shallow understanding of how this modification
technique affects the runtimes of SLS solvers. Thus, we model this modification
process and conduct an empirical analysis of the hardness of logically
equivalent formulas. Our results are twofold. First, if the modification
process is treated as a random process, a lognormal distribution perfectly
characterizes the hardness; implying that the hardness is long-tailed. This
means that the modification technique can be further improved by implementing
an additional restart mechanism. Thus, as a second contribution, we
theoretically prove that all algorithms exhibiting this long-tail property can
be further improved by restarts. Consequently, all SAT solvers employing this
modification technique can be enhanced.

23
The categories of this paper are: solv-int
19
The categories of this paper are: eess
33
The categories of this paper are: plasm-ph
21
The categories of this paper are: adap-org
37
The categories of this paper are: supr-con
15
The categories of this paper are: nucl-ex
12
The categories of this paper are: nucl-th
22
The categories of this paper are: chao-dyn
20
The categories of this paper are: acc-phys
24
The categories of this paper are: dg-ga
34
The categories of this paper are: chem-ph
5
The categories of this paper are: gr-qc
4
The categories of this paper are: cond-mat
2
The categories of this paper are: math
8
The categories of this paper are: hep-ex
36
The categories of this paper are: cmp-lg