There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g.

We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization.

Suppose we want to transmit messages across a noisy channel to a receiver. The maximum rate of transmission such that the receiver may recover the original message without errors (i.e., zero error) is called zero error capacity of the channel.

In this talk, we will be introducing the topic of distance-preserving subgraphs, and presenting some of our own results on distance-preserving subgraphs for interval graphs (joint work with Jaikumar).