Computer Science/Discrete Mathematics

Date:
Jan
31
2022

Computer Science/Discrete Mathematics Seminar I

Algorithmizing the Multiplicity Schwartz-Zippel Lemma
Prahladh Harsha
11:15am|Simonyi 101 and Remote Access

The degree mantra states that any non-zero univariate polynomial of degree at most d has at most d roots (counted with multiplicity). A generalization of this to the multivariate setting, proved by Dvir-Kopparty-Saraf-Sudan asserts that over any...

Feb
01
2022

Computer Science/Discrete Mathematics Seminar II

Bounds for subsets of $\mathbb{F}_p^n \times \mathbb{F}_p^n$ without L-shaped configurations
10:30am|Simonyi Hall 101 and Remote Access

I will discuss the difficult problem of proving reasonable bounds in the multidimensional generalization of Szemerédi's theorem. Most of the first talk will be spent going over Shkredov's proof of good bounds for sets lacking corners, in preparation...

Feb
14
2022

Computer Science/Discrete Mathematics Seminar I

Random algebraic varieties and their applications to hardness of approximation
11:15am|Simonyi 101 and Remote Access

This talk will serve as an introduction to the random algebraic method. This method has its origins in the following problem: suppose the binomial random graph comes "close" to having some property of interest P, but fails to do so because of the...