CombOpt ReadingGroup - Nathan Benedetto Proenca-Why are SDP Rounding Algorithms Randomized?

Abstract: Randomization is a powerful technique within theoretical computer science. There is strong theoretical picture studying distinct complexity models with access to random bits, in particular focused on what types of algorithms can be de-randomized. This discussion will not venture into this part of the literature, rather questioning an implicit assumption present when discussing the need for random bits. Why is randomness helpful at all, in particular in the design of rounding algorithms in the SDP literature? Granted, the value of randomness in other contexts is quite explicit. For example, a quicksort implementation uses randomization to avoid worst case inputs. The probabilistic method allows for simple constructions of complex objects by harvesting complexity from a randomness source. But what purpose does randomness serve when rounding a SDP solution into a solution to a NP-hard problem? Why Goemans and Williamson had to use a random hyperplane to turn vectors in the hypersphere into a edge-cut in a graph? This talk attempts to answer this question by presenting a couple of theorems which connect the existence of randomized rounding algorithms to cornerstone results in functional analysis.