2019-2020 Seminars

A pseudodeterministic algorithm for a search problem (introduced by Goldwasser and Gat) is a randomized algorithm that must output the *same* correct answer with high probability over all choices of randomness. In this talk I will give several...

Randomness can provide an exponential saving in the amount of communication needed to solve a distributed problem, and the canonical example of this is the equality function. However, in many examples where randomness helps, having an efficient way...

Causal inference from observational data is a vital problem, but it comes with strong assumptions. Most methods require that we observe all confounders, variables that affect both the causal variables and the outcome variables. But whether we have...

I will discuss some recent results showing that the sum-of-squares SDP hierarchy can be used to find approximately optimal solutions to k-CSPs, provided that the instance satisfies certain expansion properties. These properties can be shown to...

Function approximators, like deep neural networks, play a crucial role in building machine-learning based intelligent systems. This talk covers three core problems of function approximators: understanding function approximators, designing new...

Online learning is a popular framework for sequential prediction problems. The standard approach to analyzing an algorithm's (learner's) performance in online learning is in terms of its empirical regret defined to be the excess loss suffered by the...

We make the case that over the coming decade, computer assisted reasoning will become far more widely used in the mathematical sciences. This includes interactive and automatic theorem verification, symbolic algebra, and emerging technologies such...

The importance of analyzing big data and in particular very large networks has shown that the traditional notion of a fast algorithm, one that runs in polynomial time, is often insufficient. This is where property testing comes in, whose goal is to...

Given an increasing family F in {0,1}^n, its measure according to mu_p increases and often exhibits a threshold behavior, growing quickly as p increases from near 0 to near 1 around a specific value p_c. Thresholds of families have been of great...