Extending Partial Functions

Gunjan Kumar
Friday, 9 Nov 2018, 17:15 to 18:45
A-201 (STCS Seminar Room)
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).