An Improved Line-Point Low-Degree Test for Polynomials Over Finite Fields - Lecture

Attend a Computer Science/Discrete Mathematics Seminar featuring Prahladh Harsha from the Tata Institute of Fundamental Research discussing "An Improved Line-Point Low-Degree Test." Explore the latest advancements in low-degree testing for polynomials over finite fields, focusing on a robust test in the high-error regime for linear-sized fields. Learn about the resolution of a long-standing open question in the field, resulting in an O(d)-query robust test. Compare this new approach to previous results, including those by Polishchuk & Spielman, Arora & Sudan, and Raz & Safra. Delve into the main technical innovation: a novel bivariate analysis that leverages Hensel lifting to connect multivariate factorization with low-degree polynomial testing. Gain insights into the non-black-box application of this technique in the context of root-finding. Discover the collaborative efforts behind this research, involving Mrinal Kumar, Ramprasad Saptharishi, and Madhu Sudan.

am|Simonyi 101 and Remote Access