∑math20

Theoretical computer science · Result 138

Subset Sum in \(O(2^{0.49n})\) time

2 papers

Gives a uniform randomized classical algorithm for worst-case Subset Sum in ordinary \(O(2^{0.49n})\) word-RAM time on polynomial-bit inputs, where n counts the integers. The time bound holds on every execution and success probability is at least 2/3 on every input. Inputs may repeat positive integers; words have \(O(n+b)\) bits for maximum input bit length b.

Watch

▶Introduction: the problem and why it mattersin preparation
▶The presented solutionin preparation

Papers 2

First page of Subset Sum in Time $`O(2^{0.49n})`$

Subset Sum in Time \(O(2^{0.49n})\)

OpenAI · October 4, 2026

We give a uniform randomized classical algorithm for Subset Sum with bounded error and worst-case running time \(O(2^{0.49n})\) on polynomial-bit inputs in a word-RAM model, where n is the number of input integers. The time bound holds on every random execution.

Read PDF Download Source

Cite
@misc{OAI:Subset-Sum-in-Time-2-power-0-49n-October-4-2026,
  author = {{OpenAI}},
  title = {{Subset Sum in Time $O(2^{0.49n})$}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf}{OAI:Subset-Sum-in-Time-2-power-0-49n-October-4-2026}},
  year = {2026}
}
First page of A Low-Space Algorithm for Worst-Case Subset Sum

A Low-Space Algorithm for Worst-Case Subset Sum

OpenAI · September 26, 2026

We give a uniform classical randomized decision algorithm for worst-case Subset Sum. Under every fixed polynomial bound on input-integer bit length, it uses \(\mathop{\mathrm{poly}}\nolimits (n)2^{n/2}\) time and ordinary \(O(2^{n/5})\) writable words of \(O(n+b)\) bits, where b is the largest input bit length. Both resource bounds hold on every execution. The error is one-sided: the algorithm always rejects unsolvable instances and accepts each solvable instance with probability at least 2/3.

Read PDF Download Source

Cite
@misc{OAI:A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026,
  author = {{OpenAI}},
  title = {{A Low-Space Algorithm for Worst-Case Subset Sum}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026/paper.pdf}{OAI:A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026}},
  year = {2026}
}

Formal verification

No Lean formalization is listed for this result yet. The repository notes that unformalized results could have issues.