Partial Function Extension with Applications to Learning and Property Testing



Tuesday, 20 October 2020, 14:00 to 15:00

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 $n$ 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 linearity. 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.

Zoom link: