Valiant (1979) showed that unless $P = NP$, there is no polynomial-time algorithm to compute the number of perfect matchings of a given graph --- even if the input graph is bipartite.
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.
The stable marriage problem consists of a bipartite graph $G = (A \cup B,E)$ where every vertex has a ranking of its neighbours in a strict order of preference. Every stable matching matches the same subset of vertices.
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).
In this talk, we will study the PhD-work of Risi Kondor in which he demonstrates how bispectrum invariants can be used to classify translated and rotated images.