log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
Randomness (and derandomization) in algorithm design
David Harris
Virtual-https://umd.zoom.us/j/987598160
Wednesday, April 15, 2020, 11:00 am-12:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

Randomization is a powerful and versatile technique in algorithm design. We describe a number of applications where it can be used for distributed algorithms, and combinatorial optimization. Among other advantages, it leads to complex coordination and load-balancing almost for free.

 

Paradoxically, one of the most powerful uses of randomness is to get deterministic algorithms. These deterministic algorithms are, in turn, building blocks for other randomized algorithms. We describe some examples for hypergraph matching and the Lovasz Local Lemma. In the hypergraph matching algorithm, this maneuver is repeated twice --- we start with a simple randomized rounding algorithm that is derandomized. Combining this deterministic algorithm with an additional randomized sparsification step gives an exponentially more efficient randomized  algorithm.  Then this new randomized algorithm can itself be derandomized to give an exponentially more efficient deterministic algorithm.

 

We conclude with discussions about applications to randomness in other areas including clustering, statistical physics, and future directions.

Bio

 

David Harris is an affiliate professor at the University of Maryland. He received a Bachelor of Science in mathematics from Harvard University in 2000. He received a PhD in Applied Mathematics from the University of Maryland in 2015, advised by Aravind Srinivasan.  His research interests are in algorithm design, probability, and graph theory.

This talk is organized by Richa Mathur