Universal functions for classes of Boolean polynomials

Abstract

The following problem is considered: Find Boolean function f of n variables with the property that, given any polynomial p of degree at most s, there exists a set of n-tuples such that p is the only polynomial of degree at most s taking the same values as f at these n-tuples. It is shown that for any fixed s and sufficiently large n, such a function exists and can be chosen from among those with domains of cardinality that grow as O(n^s).