# LIDS Seminar Series

May 3, 2016

### Isoperimetric Games

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

April 12, 2016

### On Estimation with Strategic Sensors

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

March 29, 2016

### Random Walks that Find Perfect Objects and the Lovasz Local Lemma

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

March 22, 2016

### Generalized Independent Component Analysis over Finite Alphabets

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

March 16, 2016

### The Central Role of Physical Modeling in Systems Design

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

March 15, 2016

### Why Only Us: The Evolution of Language

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

March 1, 2016

### On Programs that Learn to Write Programs

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

February 23, 2016

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

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 to be an...

February 16, 2016

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

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