Title:
Partial Function Extension with Applications to Learning and Property Testing
Partial Function Extension with Applications to Learning and Property Testing
Author(s)
Bhaskar, Umang
Advisor(s)
Editor(s)
Collections
Supplementary to
Permanent Link
Abstract
In partial function extension, we are given a partial function consisting of 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 total function defined on the domain, that additionally satisfies a given property, such as convexity. This basic problem underlies research questions in many areas, such as learning, property testing, and game theory. We present bounds on the complexity of partial function extension to subadditive, submodular, and convex functions, and present applications to learning as well as property testing for these functions.
This is joint work with Gunjan Kumar.
Sponsor
Date Issued
2019-10-18
Extent
56:41 minutes
Resource Type
Moving Image
Resource Subtype
Lecture