期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A (k) -biased sample space is a distribution over 01n that -fools every nonempty linear test of size at most k. Since they were introduced by Naor and Naor [SIAM J. Computing, 1993], these sample spaces have become a central notion in theoretical computer science with a variety of applications.
When constructing such spaces, one usually attempts to minimize the seed length as a function of nk and . Given such a construction, if we reverse the roles and consider a fixed seed length, then the smaller we pick k, the better the bound on the bias becomes. However, once the space is constructed we have a \emph{single} bound on the bias of all tests of size at most k.
In this work we consider the problem of getting ``more mileage" out of (k) -biased sample spaces. Namely, we study a generalization of these sample spaces which we call \emph{gradual} (k) -biased sample spaces. Roughly speaking, these are sample spaces that -fool linear tests of size \emph{exactly} k and moreover, the bound on the bias of linear tests of size ik decays as i gets smaller.
We show how to construct gradual (k) -biased sample spaces of size comparable to the (non-gradual) spaces constructed by Alon et al. [FOCS 1990]. Our construction is based on the lossless expanders of Guruswami et al.[J. ACM, 2009], combined with the Quadratic Character Construction of Alon et al. [FOCS 1990].
