We study the problem of low-bandwidth non-linear computation on Reed-Solomon encoded data. Given an n, k Reed-Solomon encoding of a message vector 𝐟 ∈ 𝔽qᵏ, and a polynomial g ∈ 𝔽qX₁, X₂, …, Xₖ, a user wishing to evaluate g (𝐟) is given local query access to each codeword symbol. The query response is allowed to be the output of an arbitrary function evaluated locally on the codeword symbol, and the user’s aim is to minimize the total information downloaded in order to compute g (𝐟). This problem has been studied before for linear functions g; in this work we initiate the study of non-linear functions by starting with quadratic monomials. For q = pᵉ and distinct i, j ∈ k, we show that any scheme evaluating the quadratic monomial g₈, ₉: = Xᵢ Xⱼ must download at least 2 log₂ (q-1) - 3 bits of information when p is an odd prime, and at least 2log₂ (q-2) -4 bits when p = 2. When k = 2, our result shows that one cannot do significantly better than the naive bound of k log₂ (q) bits, which is enough to recover all of 𝐟. This contrasts sharply with prior work for low-bandwidth evaluation of linear functions g (𝐟) over Reed-Solomon encoded data, for which it is possible to substantially improve upon this bound Venkatesan Guruswami and Mary Wootters, 2016; Tamo et al. , 2018; Shutty and Wootters, 2021; Kiah et al. , 2024; Con and Tamo, 2022. Some proofs have been omitted from this extended abstract; the full version can be found at Keller Blackwell and Mary Wootters, 2025.
Blackwell et al. (Thu,) studied this question.