The instance encoding of Theorem 7.4 has length polynomial in
ProvedTwoFoldOPI.encode_length_leoptimal-polynomial-intersectionuniformity
There are constants such that for every instance of Theorem 7.4 (field , an matrix, a tag, forbidden values and a precision ) the public bit encoding satisfies
The encoding writes , , the coefficients of , , and in self-delimiting binary, and field elements with bits each. All these lengths are polynomial in , , and . So a running time polynomial in the size parameter also allows reading the whole encoding.
Formalization Note. Input.scale x = m + r + F.q + t with F.q = p ^ natDegree f.
Preamble
import Mathlib import Definitions.Def_TwoFoldOPI_Input
Formal statement
namespace TwoFoldOPI theorem encode_length_le : ∃ a b : ℕ, ∀ x : Input, x.encode.length ≤ a * (x.scale + 1) ^ b := by sorry end TwoFoldOPI
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held), §7.3, Theorem 7.4, p.40 ("running in poly(m, q, log(1/ϵ)) time") and §5.2 "Computational conventions", p.26; the encoding is TwoFoldOPI.Input.encode and the size parameter TwoFoldOPI.Input.scale.