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