  In partial function extension, 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 convexity.
This basic problem underlies research questions in many areas, such as
learning, property testing, and game theory. We formally study the problem of
extending partial functions to satisfy fundamental properties in combinatorial
optimization, focusing on upper and lower bounds for extension and applications
to learning and property testing.
  (1) For subadditive functions, we show the extension problem is
coNP-complete, and we give tight bounds on the approximability. We also give an
improved lower bound for learning subadditive functions, and give the first
nontrivial testers for subadditive and XOS functions.
  (2) For submodular functions, we show that if a partial function can be
extended to a submodular function on the lattice closure (the minimal set that
contains the partial function and is closed under union and intersection) of
the partial function, it can be extended to a submodular function on the entire
domain. We obtain algorithms for determining extendibility in a number of
cases, including if $n$ is a constant, or the points are nearly the same size.
The complexity of extendibility is in general unresolved.
  (3) Lastly, for convex functions in $\mathbb{R}^m$, we show an interesting
juxtaposition: while we can determine the existence of an extension
efficiently, computing the value of a widely-studied convex extension at a
given point is strongly NP-hard.
