An Improved Line-Point Low-Degree Test for Polynomials Over Finite Fields - Lecture
Offered By: Institute for Advanced Study via YouTube
Course Description
Overview
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.
Syllabus
am|Simonyi 101 and Remote Access
Taught by
Institute for Advanced Study
Related Courses
Intermediate AlgebraUniversity of California, Irvine via Coursera Visualizing Algebra
San Jose State University via Udacity College Algebra
San Jose State University via Udacity Комбинаторика для начинающих
Moscow Institute of Physics and Technology via Coursera Álgebra básica
Universidad Nacional Autónoma de México via Coursera