Noncommutative Geometry Seminar

Date: February 12, 2021

Time: 1:00PM - 2:00PM

Location: Zoom 951 5490 42

Speaker: Henry Yuen, Columbia University

Title: Testing low-degree polynomials in the noncommutative setting

Abstract: 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 )

URL: Link