Explicit Interpolation Sets Using Perfect Hash Families
Authors: Xiaodong Sun
ABSTRACT
Let $S$ be a set of functions with common domain $D$.
We say $X$, a subset of $D$, an interpolation set for
$S$ if the values on $X$ uniquely determine a function $f$ in $S$.
Recently, Piotr Indyk gave an explicit construction of
interpolation sets of size $O(k^4 \log ^4 n)$
for the family of boolean functions on $n$ variables
which depend symmetrically on at most $k$ variables.
Using perfect hash families,
we have a variant of Indyk's method to get an explicit construction
of interpolation sets of size $O(k^{10}\log n\log\log n/\log\log\log n)$
for this family of functions.
DIMACS Home Page