In this series of three posts I want to discuss some recent and old advances in discrepancy theory and their applications to algorithms. Discrepancy minimization is quite a rich and beautiful area as evidenced in these two books. Here I will focus on a specific perspective -- that of ``Beating the Union Bound'' -- which … Continue reading Discrepancy and Beating the Union Bound

"Balls and Bins?", you ask, "Is there anything left to prove there?" Surprisingly, there are really natural questions that are open. Today I want to talk about one such question. First a quick primer. Balls and Bins processes model randomized allocations processes, used in hashing or more general load balancing schemes. Suppose that I have … Continue reading Balls and Bins on Graphs