Computer Science/Discrete Mathematics Seminar I

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 inherent "long Poisson tails"; what can we do to overcome this? It turns out that in such situations, it is often possible to construct graphs using the zeros of random polynomials that actually have said property P. 

I shall illustrate this method by discussing the easiest applications in detail, and then outline how this method has recently found applications, in recent work with Boris Bukh and Karthik C.S., in establishing computational hardness results for a few basic problems. As a taste of what is to come, this approach easily allows us to construct graphs that have stronger guarantees than the celebrated norm graphs of Kollar, Ronyai, and Szabo, as far as applications to hardness of approximation are concerned.