Computer Science and Discrete Mathematics (CSDM)

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

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

In the max cut problem, we are given an n-vertex graph and we are asked what is the maximum fraction of edges "cut" by any partition of the vertices? This problem can be reformulated as an optimization problem over the cut polytope, which has...

Some of the central questions in complexity theory address the amortized complexity of computation (also sometimes known as direct sum problems). While these questions appear in many contexts, they are all variants of the following: 

Is the best...

What edge density of a graph guarantees that that it will contain a particular subgraph? Or one of a given family F of subgraphs? The celebrated Erdős--Stone--Simonovits Theorem characterizes the maximum edge density in F-free graphs, in terms of...

Bernstein's theorem (also known as the Bernstein-Khovanskii-Kushnirenko theorem) gives a bound on the number of nonzero solutions of a polynomial system of equations in terms of the mixed volume of its Newton polytopes. In this talk, we will give...