Theory of Computing Seminar

I'll discuss the problem of maximizing a monotone submodular function under noise. There has been a great deal of work on optimization of submodular functions since the 1970s, but in many many applications we do not have access to a submodular function but rather some erroneous or noisy version of it. This raises the question of whether provable guarantees are obtainable in presence of error and noise.  I'll discuss some surprising limitations and sketch an algorithm which achieves an optimal approximation guarantee in the presence of noise.