Spring 2016

February 16, 2016

How to Predict When Estimation is Hard: Algorithms for Learning on Graphs

Speaker: Sasha Rakhlin (University of Pennsylvania)

We consider the problem of predicting a binary label for an individual given the information about the person and her position within a network. Such a fusion of the two sources of information naturally arises in a variety of applications,...

February 23, 2016

When Your Big Data Seems Too Small: Accurate Inferences Beyond the Empirical Distribution

Speaker: Gregory Valiant (Stanford)

We discuss two problems related to the general challenge of making accurate inferences about a complex distribution, in the regime in which the amount of data (i.e the sample size) is too small for the empirical distribution of the samples...

March 1, 2016

On Programs that Learn to Write Programs

Speaker: Adam Kalai (Microsoft Research New England)

Currently, it is humans who write the programs that are matching and surpassing human-level performance on challenge after challenge. With time, we expect more programs to be generated automatically by computers. We begin with an...

March 15, 2016

Why Only Us: The Evolution of Language

Speaker: Robert Berwick (MIT)

We are born crying, but those cries signal the first stirring of language. Within a year or so, infants master the sound system of their language; a few years after that, they are engaging in conversations. How did this remarkable,...

March 16, 2016

The Central Role of Physical Modeling in Systems Design

Speaker: Albert Benveniste (INRIA)

Physical modeling has been used for decades by control engineers, albeit for "simple" systems that can be concisely described by a math model (one or a few equations possibly involving many variables). Real systems are now complex enough so...

March 22, 2016

Generalized Independent Component Analysis over Finite Alphabets

Speaker: Meir Feder (Tel-Aviv University)

Independent component analysis (ICA) is a statistical method for transforming an observable multidimensional random vector into components that are as statistically independent as possible. Usually the ICA framework assumes a model according...

March 29, 2016

Random Walks that Find Perfect Objects and the Lovasz Local Lemma

Speaker: Dimitris Achlioptas (University of California, Santa Cruz)

At the heart of every local search algorithm is a directed graph on candidate solutions (states) such that every unsatisfactory state has at least one outgoing arc. In stochastic local search the hope is that a random walk will reach a...

April 12, 2016

On Estimation with Strategic Sensors

Speaker: C├ędric Langbort (University of Illinois, Urbana-Champaign)

Motivated by security issues such as false-data attacks in power grids, misreports in participatory sensing apps, and adversarial machine learning, we consider the problem of estimation in the presence of strategic and self-interested...

May 3, 2016

Isoperimetric Games

Speaker: Ramon van Handel (Princeton University)

That the ball has the smallest surface area among all bodies of equal volume was already known (it is said) to Dido, queen of Carthage. This isoperimetric property follows from the fact that Lebesgue measure is log-concave. The analogous...