Uniform binary field arithmetic at logarithmic width
ProvedTimeSpaceMA.GUV.fieldOperations_existscomplexity-theorycondensersfinite-fields
For each fixed positive multiplier and width , choose a field of size and its quadratic extension, where is times the binary length of the maximum of one and . Give both fields binary labels. Deterministic polynomial-time multitape algorithms compute addition and multiplication in the larger field, the labels of the two embedded coefficients and zero, and the label of an embedded primitive element of the smaller field. Widths are supplied in unary. The positive floor applies to width zero, which is outside the correctness range of the condenser.
Preamble
import Definitions.Def_TimeSpaceMA_GUVFieldOperations
Formal statement
namespace TimeSpaceMA.GUV
theorem fieldOperations_exists :
∀ a (ha : 0 < a), Nonempty (BinaryFieldArithmetic a ha) := 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