Algorithms, Randomization, and Computation
Date: Tuesday, April 16, 2019
Time: 12:00 noon
Duration: about 20 minutes
Venue: Dipartimento di Informatica, Via Salaria 113, Third Floor, Seminari Lecture Room
Speaker: Flavio Chierichetti
Title: Algorithms, Randomization, and Computation
Abstract: Probabilistic methods are nowadays one of the central pillars of algorithmic research. Successful applications can be found in all algorithmic domains, where these methods appear in (at least) three different guises. First, as the famous example of primality testing exemplifies, oftentimes the best algorithmic solution for a given problem is randomized. Second, proving the existence of certain mathematical objects (e.g. graphs with certain properties) is often a crucial step in the analysis of an algorithm. The probabilistic method offers a powerful methodology to show the existence of such objects. Third, increasingly often, the problem at hand is inherently probabilistic, or it is best modelled as a stochastic process.
I will present my own research in this general framework, showing applications to optimization, data mining, and machine learning.