2020-21 Seminars

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

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

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

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

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

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

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

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