“Relaxations and Randomness: Faster Algorithms by Doing Less”

Discrete optimization is all around us - from finding optimal cuts in a network and planning social interventions, to assigning seats at a wedding and buying groceries. In these problems, we are faced with discrete choices: at a wedding, for instance, you can’t sit 3/4 in table A and 1/4 table B (as much as you might like to do this). Many algorithms for solving discrete problems are also themselves discrete - they involve maintaining solution sets, swapping elements in or out of the set, greedily selecting the “best” element etc. However, recent work in the field of approximation algorithms has shown that discrete problems can actually be solved via continuous methods. These are known as “relaxation” techniques. At the same time, randomness has played a large role in algorithmic design, often leading to faster algorithms than their “deterministic” counterparts. Combining relaxations and randomness can yield powerful algorithms for discrete optimization that run much faster and can even utilize a fraction of the data. In this talk, we’ll explore the basics of these techniques and when they can be used. 

Speaker: Chris Harshaw
Graduate Student in Computer Science mentored by Professors Daniel A. Spielman and Amin Karbasi

Christopher Harshaw is a Ph.D. student advised by Professors Daniel Spielman and Amin Karbasi. Christopher is interested in spectral graph theory, combinatorial optimization, and applications to machine learning. He earned a B.A. in Computational and Applied Mathematics and a B.S. in Electrical Engineering from Rice University. In his free time, he enjoys composing and playing jazz music, solving puzzles, and visiting the many restaurants in New Haven.

.