posted 18 Jan 2024

Polynomial Identity Testing

Notes Randomized Algorithms Polynomial Identity Testing

To motivate the utility of randomized algorithms, we begin with the example of testing whether two numbers are equal using the least amount of information, i.e. how can we determine whether you and I picked same number while sharing the fewest digits.

Problem

More generally, if Alice has string AA and Bob BB both with length n,n, how can they determine if A=BA = B with the minimum amount of communication?

Algorithm

The algorithm is described as follows, assume that x∈R{1,2,3,…,q}nx \in_R \{1, 2, 3, \dots, q\}^n is available to both parties, Alice sends AxAx, and Bob determines whether Ax=Bx.Ax = Bx.

  • If A=B,A = B, then Ax=Bx.Ax = Bx.
  • Otherwise, if A≠BA \neq B then what is the probability that Ax≠BxAx \neq Bx?
    • This is the same as asking if (A−B)x≠0,(A - B)x \neq 0, which is the classic polynomial identity testing problem.

A deterministic algorithm must use Ω(n)\Omega(n) bits of communication — however, with the randomized algorithms that becomes Ω(log⁡n).\Omega(\log n).

Through Schwartz-Zippel, the probablity that Ax≠BxAx \neq Bx is bounded from below at (n−1)/n.(n-1)/n.