Seminars

Are factors of sparse polynomials sparse? This is a really basic question and we are still quite far from understanding it in general. In this talk, I will discuss a recent result showing that this is in some sense true for multivariate polynomials...

Constraint satisfaction problems (CSPs) are a central topic of study in computer science. A fundamental question about CSPs is as follows. Given a CSP where each constraint has the form of some predicate P and almost all of the constraints can be...

I will give a tour of some of the key concepts and ideas in proof complexity. First, I will define all standard propositional proof systems using the sequent calculus which gives rise to a clean characterization of proofs as computationally limited...

We show that, as a consequence of a remarkable new result of Attila P\'or on universal Tverberg partitions, any large-enough set $P$ of points in $\Re^d$ has a $(d+2)$-sized subset whose Radon point has half-space depth at least $c_d \cdot |P|$...

Will this procedure be finite or infinite? If finite, how long can it last? Bjorner, Lovasz, and Shor asked these questions in 1991 about the following procedure, which goes by the name “abelian sandpile”: Given a configuration of chips on the...

Recent empirical works have successfully used unlabeled data to learn feature representations that are broadly useful in downstream classification tasks. Several of these methods are reminiscent of the well-known word2vec embedding algorithm...

We answer a 1982 conjecture of Erd&‌#337;s and Simonovits about the growth of number of $k$-walks in a graph, which incidentally was studied earlier by Blakley and Dixon in 1966. We prove this conjecture in a more general setup than the earlier...

The (stochastic) gradient descent and the multiplicative update method are probably the most popular algorithms in machine learning. We introduce and study a new regularization which provides a unification of the additive and multiplicative updates...