Title: Finding Submodularity Hidden in Symmetric Difference,
Abstract: A set function $f$ on a finite set $V$ is submodular if $f(X) + f(Y) \geq f(X
\cup Y) + f(X \cap Y)$ for any pair $X, Y \subseteq V$. The symmetric
difference transformation (SD-transformation) of $f$ by a canonical set $S
\subseteq V$ is a set function $g$ given by $g(X) = f(X \vartriangle S)$ for $X
\subseteq V$,where $X \vartriangle S = (X \setminus S) \cup (S \setminus X)$
denotes the symmetric difference between $X$ and $S$. Submodularity and
SD-transformations are regarded as the counterparts of convexity and affine
transformations in a discrete space, respectively. However, submodularity is
not preserved under SD-transformations, in contrast to the fact that convexity
is invariant under affine transformations. This paper presents a
characterization of SD-stransformations preserving submodularity. Then, we are
concerned with the problem of discovering a canonical set $S$, given the
SD-transformation $g$ of a submodular function $f$ by $S$, provided that $g(X)$
is given by a function value oracle. A submodular function $f$ on $V$ is said
to be strict if $f(X) + f(Y) > f(X \cup Y) + f(X \cap Y)$ holds whenever both
$X \setminus Y$ and $Y \setminus X$ are nonempty. We show that the problem is
solved by using ${\rm O}(|V|)$ oracle calls when $f$ is strictly submodular,
although it requires exponentially many oracle calls in general.