Short lists for shortest descriptions in short time

Jason Teutsch

RECORD

Short lists for shortest descriptions in short time

Jason Teutsch

Computational Complexity · Submitted 26 Dec 2012

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim This paper presents an efficient algorithm which generates a polynomial-size list containing an optimal description for a given input string.

how it is stated · asserted 1.00 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,820 input tokens, $0.0002 reported.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.16 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.48 · compares with prior results 0.85 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v5. Results and the main claim are underlined; show every role.

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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Is it possible to find a shortest description for a binary string?	background 1.00	0.04	0.02	hedged possibility 0.56
s1	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.	background 0.98	0.05	0.04	asserted 0.86
s2	Remarkably such approximations exist.	background 0.72	0.11	0.08	asserted 1.00
s3	This paper presents an efficient algorithm which generates a polynomial-size list containing an optimal description for a given input string.	contribution 0.87	0.96	0.91	asserted 1.00
s4	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.	method 0.85	0.90	0.05	asserted 1.00
s5	Our main result extends recent work by Bauwens, Mahklin, Vereschchagin, and Zimand.	background 0.57	0.39	0.08	asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.79 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v5

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

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.

Human review

How Pith checks papers → · Full audit of this paper →

References

How the literature uses it

3 arXiv papers cite this in 10 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 6 sentences without a confident label

Uses its method or tool 1 paper

We use the same general approach and the same ingredients as in [ref] and [ref] , but, because we go straight to the target, we can take some shortcuts that render the proof simpler.[The proof given here also produces a smaller value for the constant in the theorem.]

Short lists with short programs in short time - a short proof · Introduction · 0.91

Compares with it 1 paper

We present in this note a direct proof of Theorem [ref], which is simpler and shorter than the one in [ref] .

Short lists with short programs in short time - a short proof · Introduction · 0.82

Cites it as background 1 paper

Both [ref] and [ref] prove their results regarding polynomial-time computable lists as corollaries of somewhat more general theorems.

Short lists with short programs in short time - a short proof · Introduction · 0.87

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.