DIMACS TR: 2000-28
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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-28.ps.gz
DIMACS Home Page