Computer Science and Discrete Mathematics (CSDM)

Every multivariate polynomial P(x_1,...,x_n) can be written as a sum of monomials, i.e. a sum of products of variables and field constants.  In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P...

Every multivariate polynomial P(x_1,...,x_n) can be written as a sum of monomials, i.e. a sum of products of variables and field constants.  In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P...

The study of linear spaces of matrices arises naturally (and independently) in many different areas of mathematics and computer science.  In this survey talk, I will describe some of these motivations, and state and prove some (old and new)...

A random walk on expanders, despite its strong underlying correlations, poses extremely useful pseudorandom properties. The expander hitting property and the expander Chernoff are two such classic examples. That is, the AND function and certain...

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>0c>0 such that every compact convex set KK in RnRn, of unit volume, must contain a slice (namely, a set of the form K∩HK∩H for some affine hyperplane HH) whose...

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