Seminars

The Theoretical Computer Science and Discrete Mathematics Seminars will take place every Monday at 11:15 a.m. - 12:15 p.m. and every Tuesday at 10:30 a.m. - 12:30 p.m. at the Institute for Advanced Study. The lectures will be held in S-101, the seminar room in Simonyi Hall, unless stated otherwise.

If you are interested in attending future seminars and are not already on our mailing list from previous years, please send an e-mail to Andrea Lass and ask to be added.

alass email

 

Upcoming Seminar Titles Include:

Jan
20
2021

Stability and Testability

Stability and Invariant Random Subgroups
Henry Bradford
11:00am|Remote Access
Determining whether or not a given finitely generated group is permutation stable is in general a difficult problem. In this talk we discuss work of Becker, Lubotzky and Thom which gives, in the case of amenable groups, a necessary and sufficient...
Jan
25
2021

Computer Science/Discrete Mathematics Seminar I

An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature
11:15am|Remote Access - see Zoom link below

"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...

Jan
26
2021

Computer Science/Discrete Mathematics Seminar II

Log-concave polynomials in theory and applications
10:30am|Simonyi Hall 101 and Remote Access - see Zoom link below

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...

Jan
27
2021

Stability and Testability

Stability of amenable groups via ergodic theory
Arie Levit
11:00am|Remote Access
I will describe how basic ergodic theory can be used to prove that certain amenable groups are stable. I will demonstrate our method by showing that lamplighter groups are stable. Another uncountably infinite family to which our method applies are...
Feb
01
2021

Computer Science/Discrete Mathematics Seminar I

Graph Density Inequalities, Sums of Squares and Tropicalization
Annie Raymond
11:15am|Remote Access - see Zoom link below

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...