{"id":"openai-math/Subset-Sum-in-Time-2-power-0-49n","pdf":"https://github.com/openai/math/blob/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026/subset-sum.pdf","url":"https://github.com/openai/math/tree/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026","tags":["algorithms","subset-sum","exponential-time","complexity"],"score":0,"title":"Subset Sum in Time $`O(2^{0.49n})`$","domain":"Theoretical computer science","family":"138","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-04","reactions":{},"formalized":false,"family_title":"Subset Sum in $`O(2^{0.49n})`$ time"}