{"id":"openai-math/Polynomial-Hitting-Lists-for-Noncommutative-Rational-Formulas","pdf":"https://github.com/openai/math/blob/main/preprints/Polynomial-Hitting-Lists-for-Noncommutative-Rational-Formulas-September-24-2026/Polynomial-Hitting-Lists-for-Noncommutative-Rational-Formulas-September-24-2026.pdf","url":"https://github.com/openai/math/tree/main/preprints/Polynomial-Hitting-Lists-for-Noncommutative-Rational-Formulas-September-24-2026","tags":["computational-complexity","noncommutative-algebra","derandomization"],"score":0,"title":"Polynomial Hitting Lists for Noncommutative Rational Formulas","domain":"Theoretical computer science","family":"116","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We construct, in deterministic polynomial bit time, a polynomial-size list of rational matrix tuples for noncommutative rational formulas over ℚ of bounded tree size. Every nonzero admissible formula has a defined, invertible value at one tuple, with no separate bounds on inverse nesting or rational constant heights. Matrix dimensions, entry bit lengths, and total output length are polynomially bounded.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":true,"family_title":"Uniform black-box noncommutative identity testing across characteristics"}