Henry Yuen
(Columbia University)
February 12, 2021
Organized by Americas GNCG Seminar.

Testing low-degree polynomials in the noncommutative setting

In low-degree testing the following question is considered: given a multivariate function over a finite field, if a sufficiently large fraction of “local views” of the function are consistent with low-degree polynomials, does this imply that the function is _globally_ consistent with a single low-degree polynomial? Many low-degree testing theorems have been proved over the years, and have had important applications in theoretical computer science, including complexity theory and property testing.

Low-degree testing also plays an important role in the recent quantum complexity result MIP* = RE. Here, low-degree testing is considered in the _noncommutative_ setting: “local views” of a function are given via a sequence of measurements on a state, but the measurement operators do not necessarily commute with each other. Despite noncommutativity, there is still a sense in which local consistency with low-degree polynomials implies global consistency with low-degree polynomials.

In this talk I will give an introduction to low-degree testing and discuss its analysis. This is based on joint work with Ji, Natarajan, Vidick, and Wright. (https://arxiv.org/abs/2009.12982 )

Share on email
Share on facebook
Share on google
Share on twitter
Share on linkedin