Faculty Candidate Seminar

Structure and Randomness in Complex Systems

Shachar LovettPost DocInstitute for Advanced Studies

Complicated systems arise naturally in many scenarios. For example, huge graphs or high dimensional data are part of many problems arising in real life and in theoretical models. In other cases, the problems are simple to describe, but the set of potential solutions is very complicated. I will describe a general approach to analyze and build algorithms for complicated systems. It is based, on the one hand, on finding important structures in these systems; and, on the other hand, on identification of random-like properties that these objects possess. I will give several examples for the usefulness of this approach.
Shachar Lovett is a post-doc at the Institute for Advanced Study in Princeton, NJ. He is interested in the relations between structure, randomness and pseudo-randomness in many areas of mathematics and computer science, and in particular in
computational complexity, additive combinatorics and coding theory.

Sponsored by