2020-21 Seminars

Expander graphs are graphs which simultaneously are both sparse and highly connected. The theory of expander graphs received a lot of attention in the past half a century, from both computer science and mathematics. In recent years, a new theory of...

Non-constructive existence proofs, which establish the existence of objects without furnishing an efficient algorithm to produce examples, abound in mathematics. How hard is it, computationally, to find objects whose existence is guaranteed non...

A polynomial with nonnegative coefficients is strongly log-concave if it and all of its derivatives are log-concave as functions on the positive orthant. This rich class of polynomials includes many interesting examples, such as homogeneous real...

Establishing inequalities among graph densities is a central pursuit in extremal graph theory. One way to certify the nonnegativity of a graph density expression is to write it as a sum of squares or as a rational sum of squares. In this talk, we...

A polynomial with nonnegative coefficients is strongly log-concave if it and all of its derivatives are log-concave as functions on the positive orthant. This rich class of polynomials includes many interesting examples, such as homogeneous real...

"Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly. Estimating the value of such games (i.e., winning probability under optimal play by the strategic player) is an...