BARC talk by Prahladh Harsha

Wednesday, October 23, 2024, Prahladh Harsha, professor at the Tata Institute of Fundamental Research (TIFR) in Mumbai, India, will give a talk on "An Improved Line-Point Low-Degree Test".

Abstract:
A natural test to test if a given function $f: F^m \to  F$ is a low-degree polynomial is to choose a random line $\ell$ and check if the restriction of the function $f$ to the line $\ell$ is a univariate low-degree polynomial. In this talk, he will show that this natural low-degree test for polynomials over finite fields is "robust"' in the high-error regime for linear-sized fields. This settles a long-standing open question in the area of low-degree testing, yielding an $O(d)$-query robust test in the "high-error"' regime. The previous results in this space either worked only in the "low-error" regime or required $q= \Omega(d^4)$, or needed to measure local distance on 2-dimensional "planes"' rather than one-dimensional lines leading to $\Omega(d^2)$-query complexity.

The main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection (namely Hensel lifting) between multivariate factorization and finding (or testing) low-degree polynomials, in a non "black-box'" manner in the context of root-finding.

[Joint work with Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan]

Bio:
Prahladh Harsha is a member of the faculty of the School of Technology and Computer Science (STCS) at the Tata Institute of Fundamental Research (TIFR), Mumbai. He was a graduate student at the Massachusetts Institute of Technology (MIT), where he obtained his PhD under the supervision of Prof. Madhu Sudan. Then he did a postdoc at Microsoft Research-Silicon Valley, and after that a research assistant professor at the Toyota Technological Institute at Chicago.

Host: 
Skrikanth Srinivasan