2020-21 Seminars

May
10
2021

Computer Science/Discrete Mathematics Seminar I

A Complexity-Theoretic Perspective on Fairness
Michael P. Kim
11:15am|Simonyi Hall 101 and Remote Access - see Zoom link below

Algorithms make predictions about people constantly.  The spread of such prediction systems has raised concerns that algorithms may exhibit unfair discrimination, especially against individuals from minority groups.  While it's easy to speculate on...

May
04
2021

Computer Science/Discrete Mathematics Seminar II

On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture and Bourgain's slicing problem - Part III
10:30am|Simonyi Hall 101 and Remote Access - see Zoom link below

This is the final talk in a 3-part series whose goal is to give background as well as a self contained proof of Chen's recent breakthrough on the KLS conjecture and slicing problem. After becoming familiar with the construction of stochastic...

Apr
26
2021

Computer Science/Discrete Mathematics Seminar II

On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture and Bourgain's slicing problem - Part II
10:30am|Simonyi Hall 101 and Remote Access - see Zoom link below

This is the second talk in a 3-lecture series whose goal is to give background as well as a self contained proof of Chen's recent breakthrough on the KLS conjecture and slicing problem (a video of the first lecture can be found here:

https://www...

Apr
20
2021

Computer Science/Discrete Mathematics Seminar II

On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture and Bourgain's slicing problem
10:30am|Simonyi Hall 101 and Remote Access - see Zoom link below

In the mid 80's, Bourgain asked the following question: Is there a universal constant $c>0$ such that every compact convex set $K$ in $R^n$, of unit volume, must contain a slice (namely, a set of the form $K \cap H$ for some affine hyperplane $H$)...

Apr
12
2021

Computer Science/Discrete Mathematics Seminar I

Privacy as Stability, for Generalization
Katrina Legitt
11:15am|Remote Access - see Zoom link below

Many data analysis pipelines are adaptive: the choice of which analysis to run next depends on the outcome of previous analyses. Common examples include variable selection for regression problems and hyper-parameter optimization in large-scale...

Apr
07
2021

Stability and Testability

Approximations of infinite groups
Goulnara Arzhantseva
11:00am|Remote Access

We discuss various (still open) questions on approximations of finitely generated groups, focusing on finite-dimensional approximations such as residual finiteness and soficity. We survey our results on the existence, stability and quantification of...

Apr
06
2021

Computer Science/Discrete Mathematics Seminar II

How difficult is it to certify that a random 3SAT formula is unsatisfiable?
10:30am|Remote Access - see Zoom link below

The Satisfiability problem is perhaps the most famous problem in theoretical computer science, and significant effort has been devoted to understanding randomly generated SAT instances. The random k-SAT model (where a random k-CNF formula is chosen...

Apr
05
2021

Computer Science/Discrete Mathematics Seminar I

Pandora's Box with Correlations: Learning and Approximation
Shuchi Chawla
11:15am|Remote Access - see Zoom link below

In the Pandora's Box problem, the algorithm is provided with a number of boxes with unknown (stochastic) rewards contained inside them. The algorithm can open any box at some cost, discover the reward inside, and based on these observations can...

Mar
31
2021

Stability and Testability

Ultrametric stability problems
Francesco Fournier-Facio
11:00am|Remote Access

We study stability problems with respect to families of groups equipped with bi-invariant ultrametrics, that is, metrics satisfying the strong triangle inequality. This property has very strong consequences, and this form of stability behaves very...

Mar
30
2021

Computer Science/Discrete Mathematics Seminar II

Computational - Statistical gaps and the Group Testing problem
10:30am|Remote Access - see Zoom link below

In a plethora of random models for constraint satisfaction and statistical inference problems, researchers from different communities have observed computational gaps between what existential or brute-force methods promise, and what known efficient...