Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Short lists for shortest descriptions in short time   Is it possible to find a shortest description for a binary string? The
well-known answer is "no, Kolmogorov complexity is not computable." Faced with
this barrier, one might instead seek a short list of candidates which includes
a laconic description. Remarkably such approximations exist. This paper
presents an efficient algorithm which generates a polynomial-size list
containing an optimal description for a given input string. Along the way, we
employ expander graphs and randomness dispersers to obtain an Explicit Online
Matching Theorem for bipartite graphs and a refinement of Muchnik's Conditional
Complexity Theorem. Our main result extends recent work by Bauwens, Mahklin,
Vereschchagin, and Zimand.

15
The categories of this paper are: nucl-ex
3
The categories of this paper are: physics
4
The categories of this paper are: cond-mat
5
The categories of this paper are: gr-qc
0
The categories of this paper are: hep-ph
9
The categories of this paper are: nlin
14
The categories of this paper are: math-ph
24
The categories of this paper are: dg-ga
23
The categories of this paper are: solv-int
27
The categories of this paper are: comp-gas
28
The categories of this paper are: alg-geom
35
The categories of this paper are: mtrl-th
31
The categories of this paper are: ao-sci
26
The categories of this paper are: bayes-an
17
The categories of this paper are: q-fin
22
The categories of this paper are: chao-dyn