In this talk we describe why backward deterministic Büchi automata are interesting, how they are defined, what their main features are, and how they can be applied to solve problems in temporal logic.

Suppose that we want to select a set of k>1 alternatives, and each voter indicates which of the alternatives are acceptable to her: the alternatives could be conference submissions, applicants for a scholarship or locations for a fast food chain. In this setting it is natural to require that the winning set represents the voters fairly, in the sense that large groups of voters with similar preferences have at least some of their approved alternatives in the winning set. In this talk, we show how to formalize this idea and how to use it to classify voting rules; surprisingly, two little-known rules proposed in the 19^th century turn out to play an important role in our analysis.

There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g. Nesterov's acceleration, conjugate gradient, heavy ball) for the purposes of stochastic optimization due to their instability and error accumulation, a notion made precise in d'Aspremont 2008 and Devolder, Glineur, and Nesterov 2014. This work considers the use of “fast gradient” methods for the special case of stochastic approximation for the least squares regression problem. Our main result refutes the conventional wisdom by showing that acceleration can be made robust to statistical errors. In particular, this work introduces an accelerated stochastic gradient method that provably achieves the minimax optimal statistical risk faster than stochastic gradient descent. Critical to the analysis is a sharp characterization of accelerated stochastic gradient descent as a stochastic process.

Estimating a matrix based on partial, noisy observations is prevalent in variety of modern applications with recommendation system being a prototypical example. The non-parametric latent variable model provides canonical representation for such matrix data when the underlying distribution satisfies ``exchangeability'' with graphons and stochastic block model being recent examples of interest. Collaborative filtering has been a successfully utilized heuristic in practice since the dawn of e- commerce. In this extended abstract, we will argue that collaborative filtering (and its variants) solve matrix estimation for a generic latent variable model with near optimal sample complexity.

This talk is based on joint works with Lee, Li, Shah and Song (2016) and Borgs, Chayes, Lee and Shah (2017).

Information-theoretic cryptography is chock-full of open problems with a communication-complexity flavor. We will describe several such problems that arise in the study of private information retrieval, multi-party secure computation, secret-sharing, private simultaneous messages (PSM) and conditional disclosure of secrets (CDS). In all these cases, there is a huge (exponential) gap between the best known upper and lower bounds. Our focus will be on describing the (sometimes surprising) connections between these problems, some old and some new.

Formal methods rely on a clear mathematical understanding of programs and their interactions. The goal of synthesis is to design a program that complies with a given logical specification, and reactive synthesis addresses the question in the setting where programs interact with their environment.

In recent years, synthesis of reactive, distributed programs has gained momentum. The goal is to construct automatically programs and controllers consisting of local entities that can interact in various ways, in order to guarantee a correct behavior. The talk will present that state-of-the-art and some challenges raised by the distributed setting.