MATH Seminar

Title: Probabilistic Bezout Over Finite Fields, and Some Applications
Seminar: Math Colloquia
Speaker: Bhargav Narayanan of Rutgers University
Contact: Liana Yepremyan, liana.yepremyan@emory.edu
Date: 2022-02-23 at 4:00PM
Venue: MSC W303
Download Flyer
Abstract: What is the distribution of the number of distinct roots of k random polynomials (of some fixed degree) in k variables? I will talk about a recently proved Bezout-like theorem that gives us a satisfactory answer over (large) finite fields. This result can be used to construct several interesting families of “extremal graphs”. I shall illustrate this method by 1) discussing the easiest applications in detail, reproving some well-known lower bounds in extremal graph theory, and 2) outlining how this method has recently found applications in establishing hardness results for a few basic computational problems.