期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We develop a new notion called {\it tester of a class \cM of
functions} f:\cA\cC that maps the elements \bfa\cA in
the domain \cA of the function to a finite number (the size of
the tester) of elements \bfb1\bfbt in a smaller
sub-domain \cB\cA where the property f(\bfa)=0 is
preserved for all f\cM. I.e., for all f\cM and \bfa\cA if f(\bfa)=0 then
f(\bfbi)=0 for some i.
We use tools from elementary algebra and algebraic function fields
to construct testers of almost optimal size in deterministic polynomial time in the size of the tester. We then apply testers to deterministically construct new set of objects with some combinatorial and algebraic properties that can be used to derandomize some algorithms.
We show that those new constructions are almost optimal and for many of them meet the union bound of the problem. Constructions include,
d-restriction problems, perfect hash, universal sets, cover-free families, separating hash functions, polynomial restriction
problems, black box polynomial identity testing for polynomials and circuits
over small fields and hitting sets.
