Partial function extension is a basic problem that underpins multiple research topics in optimization, including learning, property testing, and game theory. Here, we are given a partial function consisting of some points from 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 domain, that additionally satisfies a given property, such as monotonicity. We formally study partial function extension for various complement-free functions.
Our contributions are twofold. Firstly, for the properties studied, we give a combinatorial characterization and bounds on the complexity of partial function extension. Secondly, we develop new connections between partial function extension and learning and property testing, and use these to give new results for these problems.
Join Zoom Meeting
https://zoom.us/j/96720853429?pwd=ZUFFdzYvSmQzMWRNOG9PZVNzMHJpdz09
Meeting ID: 967 2085 3429
Passcode: 869836
