  The problem of repairing linear codes and, in particular, Reed Solomon (RS)
codes has attracted a lot of attention in recent years due to their extreme
importance to distributed storage systems. In this problem, a failed code
symbol (node) needs to be repaired by downloading as little information as
possible from a subset of the remaining nodes. By now, there are examples of RS
codes that have efficient repair schemes, and some even attain the cut-set
bound. However, these schemes fall short in several aspects; they require a
considerable field extension degree. They do not provide any nontrivial repair
scheme over prime fields. Lastly, they are all linear repairs, i.e., the
computed functions are linear over the base field. Motivated by these and by a
question raised in [GW17] on the power of nonlinear repair schemes, we study
the problem of nonlinear repair schemes of RS codes.
  Our main results are the first nonlinear repair scheme of RS codes with
asymptotically optimal repair bandwidth (asymptotically matching the cut-set
bound). This is the first example of a nonlinear repair scheme of any code and
also the first example that a nonlinear repair scheme can outperform all linear
ones. Lastly, we show that the cut-set bound for RS codes is not tight over
prime fields by proving a tighter bound, using additive combinatorics ideas.
