Design and Analysis of Stochastic Local Search Algorithms

Abstract:

In computer science and artificial intelligence, local search is a simple, highly successful method for solving computational tasks related to combinatorial optimization and statistical inference, which also scales and is typically amenable to parallelization.  Naturally, this widely-applied family of algorithms has been the subject of intense study for decades and, in particular, a lot of effort has been devoted to answering fundamental questions such as:  When are local search algorithms optimal? What structural properties of the input guarantee the success of local search algorithms? What fundamental barriers prohibit local search algorithms to succeed?  

In this talk, I will present a general framework for the design and analysis of stochastic local search algorithms, inspired by and extending a powerful tool of the Probabilistic Method — the so-called Lovasz Local Lemma. I will also briefly mention new approaches for obtaining upper and lower bounds on the running time of Markov Chain Monte Carlo algorithms and their connections to the computational complexity of statistical inference. 

Bio:

Fotios Iliopoulos received his Ph.D. in computer science from the University of California, Berkeley in August 2019, where he was advised by Alistair Sinclair. Currently, he is a post-doctoral researcher at the Institute for Advanced Study (September 2019 to August 2020) and Princeton University (September 2020 to August 2021).  His research interests lie in Algorithms and Probability and their applications to combinatorial optimization, sampling, and statistical inference tasks.

As a gentle reminder, please respect the privacy of faculty recruitment by not sharing the candidate status of our guests with others outside of our organization.

Zoom Link:   https://ucsc.zoom.us/j/95229314720?pwd=YnA1VzlxdGpwTStxU1QyR3RFK2NoQT09