Extending Partial Functions

Speaker: 

Time: 

Friday, 9 November 2018, 17:15 to 18:45

Venue: 

In the problem of partial function extension, we are given a partial function consisting of a set of $n$ points in a domain and a function value at each point. Our objective is to determine if this partial function can be extended to a function defined on the whole domain, that additionally satisfies a required property, such as convexity. We will show that if the set of defined points form a lattice and partial function is submodular within the lattice, then there always exists a submodular extension to the boolean hypercube (joint work with Umang Bhaskar).