文章基本信息

标题：Testers and their Applications
本地全文：下载
作者：Nader Bshouty
期刊名称：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.
关键词：Derandomization, Black Box PIT, Cover-Free families, Perfect hash, Separating hash functions, Universal sets