Episode 138, October 2026

Subset Sum in 2^0.49n?

A claimed randomized algorithm that beats meet in the middle for worst-case Subset Sum by an exponential factor

Covers result 138 in OpenAI’s catalog: all 2 papers. See its connections to other results and the work it cites.

Play Episode 138: Subset Sum in 2^0.49n? A walk of phase arrows and the single unit arrow that survives.

6:33. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

Given n positive integers and a target, is there a subset that adds up exactly to the target? Subset Sum is one of the foundational NP-complete problems, Knapsack in Karp’s list. Trying every subset takes 2ⁿ steps. Horowitz and Sahni’s 1974 meet-in-the-middle algorithm splits the numbers in half, lists and sorts the subset sums of each half, and scans for a complementary pair, in about 2^n/2 steps. Schroeppel and Shamir kept that time with about 2^n/4 memory; Chen, Jin, Randolph and Servedio saved a polynomial factor (2^n/2/n^γ with γ > 0.5023); representation methods of Howgrave-Graham and Joux and of Becker, Coron and Joux go faster on random instances, without a guarantee for every input. As the new paper puts it, a fixed reduction of the exponential rate below one half is a different objective from such polynomial-factor savings.

Result 138 is an OpenAI preprint (33 pages, October 4, 2026) with a separate companion (36 pages, September 26, 2026). The headline claims a randomized algorithm that, for n numbers of at most n^c bits (any fixed c), decides Subset Sum on every run in at most C_c·2^0.49n word operations, in a word RAM with words of about 4(n + b) bits, and answers correctly with probability at least 2/3 on every input. The analysis gives 2^0.489995n times a polynomial, rounded up to 0.49; small inputs and enormously long numbers fall back to ordinary meet in the middle, and nothing is assumed about how the numbers are distributed. The companion keeps the 2^n/2 time but uses only (n+b+2)¹⁵·2^0.199n words of memory, so O(2^n/5), and never answers yes wrongly. Neither paper cites the other.

What it doesn’t claim

A deterministic algorithm, a practical speedup, or any bound for numbers with super-polynomially many bits. The gain 2^0.01n is a factor of 2 at n = 100 and 4 at n = 200, and by our arithmetic it outgrows a single factor of n only from n = 997; the constants are not given. The headline makes no claim about memory, and the companion makes none below 2^n/2 time. The 2^0.246n memory bound the companion cites from earlier work (Belova, Chukhin, Kulikov and Mihajlin) is for numbers of magnitude 2^O(n).

Where it stands

Posted as a preprint: OpenAI, 33 pages, dated October 4, 2026, with a 36-page companion dated September 26, 2026
Peer reviewed: Not yet
Checked in Lean: Not the headline. The companion’s main theorem has an uncatalogued Lean proof, which we have not built

Last checked October 19, 2026. Neither preprint has been revised. The headline is not formalized in Lean, and the release’s catalog lists no Lean proof for this result. The repository does contain an uncatalogued Lean formalization of the companion: its main theorem states one-sided correctness, success probability at least 2/3, and operation and storage counts of order 2^n/2 and 2^0.199n on every outcome (633 files and 86,107 lines with its imports, not counting Mathlib, with no unproved steps that we could find). We have not built it, and have not checked how its counts match the paper’s word RAM. The papers are not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

One solution. Multiply every number by a large multiplier, add a small random tie-breaking weight, and try polynomially many shifted targets. If a solution exists, then with probability at least 11/12 some target has exactly one (the isolation lemma of Mulmuley, Vazirani and Vazirani).
Deficiency. The deficiency of a set of numbers is how many powers of two you save by storing only its distinct subset sums. The algorithm first runs meet in the middle with duplicates removed, stopping once a list passes 2^{⌈0.489985n⌉}; that reliably finishes when a typical half has expected deficiency above 0.01004n.
A checksum that cancels. Otherwise, pick a random prime P and random phases, so each subset gets a point on the unit circle. The phase sum over subsets hitting the target modulo P, minus the phase sum over aliases (subsets hitting it modulo P but not exactly), is the phase sum over true solutions: zero if there are none, a single unit phase if the solution is unique.
Loud frequencies. Both sums are huge and must be subtracted to small absolute error, and P has about 0.52n bits. Fourier inversion writes the modular sum as an average over frequencies, but each term’s square averages 2ⁿ, carried by rare loud values. Random filters, related to locality-sensitive filtering, find them, and each sample is divided by its number of matches.
Listing aliases. A representation technique (random sign flips, a shared block of coordinates, a small prime filter, and a rule that skips every pair hitting the exact target) lists every alias. It needs a block with many distinct sums, which is exactly the low-deficiency case. The three costly steps land at 0.489985, 0.48996 and 0.4899602 in the exponent.

The numbers in the video

Meet in the middle on 41, 34, 21, 20, 8, 7, 7, 4 with target 100: 14 and 12 distinct half sums; the scan finds 82 + 18 on its 14th step.
Distinct subset sums of 20 numbers: 1,048,576 for powers of two, 211 for 1 to 20, 21 when all are equal.
1 to 16 with target 40 has 498 solutions; random tie weights left the lightest unique in 98.9% of 20,000 trials.
With 14 numbers and P = 101, a bin of 165 subsets adds up to a vector of length 12.98; subtracting its 164 aliases leaves one arrow of length exactly 1, and a target with no solution leaves 0.
Over 10⁶ random phase draws, |J|² had mean close to 2¹⁴ but median 2.2, with the top 1% of draws carrying 79% of the total.

Read the source

Subset Sum in Time O(2^0.49n) (PDF), 33 pages.
A Low-Space Algorithm for Worst-Case Subset Sum (PDF), 36 pages.
The companion’s uncatalogued Lean main file.
The collection’s catalog, where this is result 138.

The 2 papers in this result

OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.

Subset Sum in Time O(2^(0.49n)) main paper
A Low-Space Algorithm for Worst-Case Subset Sum companion

Transcript

Read the full script

0:00Splitting in half

Given some positive whole numbers and a target, is there a subset that adds up exactly to the target? This is Subset Sum, one of the foundational NP-complete problems; it appears as Knapsack in Karp’s list. With n numbers there are 2^n subsets to try. The classic shortcut, by Horowitz and Sahni, splits the numbers in half. Take these eight numbers and the target 100. List the distinct subset sums of each half, 14 on the left and 12 on the right, and sort them. Then scan the left list upward and the right list downward, looking for a pair that adds up to the target. After 14 steps: 82 + 18, that is 41, 21 and 20, with 7, 7 and 4. The work is about 2^(n/2), instead of 2^n. Schroeppel and Shamir kept that time while cutting the memory to about 2^(n/4). In 2023, Chen, Jin, Randolph and Servedio saved a polynomial factor, a power of n a little above one half. Representation methods, introduced by Howgrave-Graham and Joux and developed by Becker, Coron and Joux, go faster on random instances, but give no guarantee for every input. And Austrin, Kaski, Koivisto and Nederlof exploited blocks of numbers with many distinct subset sums, or with few. As the new paper puts it, lowering the exponent of one half by a fixed amount is a different objective from polynomial savings.

1:28The claim

Result 138 is two OpenAI preprints. The headline, 33 pages, dated October 4, claims a randomized algorithm that decides Subset Sum, on every input whose numbers have polynomially many bits, in at most a constant times 2^(0.49n) word operations, on every run, answering correctly with probability at least two thirds. The analysis actually gives 2^(0.489995n) times a polynomial, rounded up to 0.49. Small inputs, and ones with enormously long numbers, fall back to ordinary meet in the middle, so the answer is right with that probability on every input, and nothing is assumed about how the numbers are distributed. The gain is small and asymptotic. Two to the point oh one n is a factor of two at a hundred numbers and four at two hundred, and by our arithmetic it outgrows even a single factor of n only beyond about a thousand numbers. The constants are not given. The second preprint, 36 pages, dated September 26, is a separate companion result: it keeps the 2^(n/2) time, and uses only about 2^(n/5) words of memory, below the 2^(0.246n) it cites from earlier work for numbers of about n bits, and it never wrongly answers yes. Neither paper cites the other. The headline has no Lean proof, but the repository holds an uncatalogued Lean formalization of the companion’s main theorem.

3:02How the proof goes

The headline proof starts by making the answer unique. Multiply every number by a large multiplier, add a small random tie-breaking weight, and try polynomially many shifted targets: if a solution exists, then with probability at least 11/12 some target has exactly one. In our run, the numbers 1 to 16 have 498 subsets summing to 40, and the lightest one was unique in about 99 percent of trials. Next comes what the paper calls deficiency: how many powers of two you save by storing only the distinct subset sums, because many subsets share a sum. 1 to 20 has only 211 distinct subset sums, out of about a million subsets. So the algorithm first runs meet in the middle with duplicates removed, stopping if a list grows past about 2^(0.49n). That reliably finishes when a typical half has deficiency above about one percent of n. Otherwise, a typical half has deficiency below about one percent of n, and the paper uses a checksum. Pick a random prime P and random phases, so that each subset gets a point on the unit circle. Add up the phases of all subsets that hit the target modulo P, then subtract the aliases: subsets that hit it modulo P, but not exactly. What remains is exactly the phases of the true solutions: nothing, if there are none, and one arrow of length one if the solution is unique. In our run with 14 numbers and P equal to 101, the bin held 165 subsets, adding up to a vector of length about 13; after subtracting 164 aliases, a single arrow of length one remained. For a target with no solution, nothing remained. Both sums are huge, and their difference must be found to small absolute error. The prime has about 0.52n bits, so scanning its residues is unaffordable. Fourier inversion writes the bin as an average over frequencies, but at each frequency, a term’s square averages 2^n, carried by rare loud values: in our simulation the median was about two, and the loudest one percent of draws carried about 80 percent of the total. So the paper looks for loud frequencies with random filters, related to locality-sensitive filtering, and divides each sample by how many matches represent it. The aliases are listed with a representation technique: random sign flips, a shared block of coordinates, a small prime filter, and a rule that skips every pair hitting the exact target. That needs a block with many distinct sums, which is exactly the low-deficiency case. The three costly steps each land just under 0.49.

5:49Where it stands

Neither preprint is peer reviewed, and neither has been revised. The headline is not formalized in Lean; the companion’s Lean proof is not listed in the catalog, and we did not build it. They are not among those OSVerify reviewed, and we have seen no expert review. If it holds, worst-case Subset Sum on numbers of polynomial bit length can be decided faster than 2^(n/2) by an exponential factor, 2^(0.01n): the exponent of one half from Horowitz and Sahni’s 1974 algorithm is not the limit. The method is randomized, and the saving is tiny at sizes anyone could run.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.

Subset Sum in 20.49n?