Uniform polynomial-time evaluation of the folded Reed–Solomon map
OpenTimeSpaceMA.GUV.foldedEvaluator_existscomplexity-theorycondensersfinite-fields
Fix a positive integer . For each input width , let , let have size , and let be a quadratic extension of . Encode an -bit input as the coefficients of a polynomial . For a primitive element and a seed , compute the packed list consisting of and the symbols
There exist bijective binary representations of these fields and a single deterministic polynomial-time multitape evaluator for this packed map, using the given unary encodings of the input and seed widths. The asserted correctness concerns only the arithmetic map.
Preamble
import Definitions.Def_TimeSpaceMA_GUVFoldedEvaluator
Formal statement
namespace TimeSpaceMA.GUV
theorem foldedEvaluator_exists (a : ℕ) (ha : 0 < a) :
∃ cond, Nonempty (FoldedEvaluator a ha cond) := by sorry
end TimeSpaceMA.GUVSource
Guruswami, Umans and Vadhan, Unbalanced Expanders and Randomness Extractors from Parvaresh–Vardy Codes, JACM 56(4), 2009, Theorem 6.3. https://www.cs.cmu.edu/~venkatg/pubs/papers/PV-condenser.pdf