Stay Informed:
Baskin Engineering COVID-19 Information and Resources
Campus Roadmap to Recovery
Zoom Links: Zoom Help | Teaching with Zoom | Zoom Quick Guide

Design and Analysis of Stochastic Local Search Algorithms

Speaker Name: 
Fotios Iliopoulos
Speaker Title: 
Postdoctoral Researcher
Speaker Organization: 
Institute for Advanced Study and Princeton University
Start Time: 
Monday, March 15, 2021 - 11:00am
End Time: 
Monday, March 15, 2021 - 12:15pm
Location: 
Via Zoom Link
Organizer: 
John Musacchio

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

Event Type: 
Event