The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known constructions of linear embeddings that satisfy the Johnson-Lindenstrauss property involve randomness. We address the question of explicitly constructing such embedding families and provide a construction with an almost optimal use of randomness: we use O(log(n delta)log(log(n delta) epsilon)) random bits for embedding n dimensions to O(log(1 delta) epsilon^2) dimensions with error probability at most delta, and distortion at most epsilon. In particular, for delta = 1 poly(n) and fixed epsilon, we use O(log n loglog n) random bits. Previous constructions required at least O(log^2 n) random bits to get polynomially small error.
The works of @cite_20 and Meka and Zuckerman @cite_13 construct pseudorandom generators for degree @math threshold functions achieving a seed-length of @math for fooling with error at most @math . As derandomizing the JL lemma is a special case of fooling degree 2 PTFs, these works give a JL family with seed-length @math .
@cite_13 @cite_20
2022644058 2138092283
We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed-length log n eO(d) fooling degree d PTFs with error at most e. Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error e. For the class of degree 1 threshold functions or halfspaces, we construct PRGs with much better dependence on the error parameter e and obtain the following results. A PRG with seed length O(log n log(1 e)) for error e ≥ 1 poly(n). A PRG with seed length O(log n) for e ≥ 1 poly(log n). Previously, only PRGs with seed length O(log n log2(1 e) e2) were known for halfspaces. We also obtain PRGs with similar seed lengths for fooling halfspaces over the @math dimensional unit sphere. The main theme of our constructions and analysis is the use of invariance principles to construct pseudorandom generators. We also introduce the notion of monotone read-once branching programs, which is key to improving the dependence on the error rate e for halfspaces. These techniques may be of independent interest. For an @math -variate degree– @math real polynomial @math , we prove that @math is determined up to an additive @math as long as @math is a @math -wise independent distribution over @math for @math . This gives a broad class of explicit pseudorandom generators against degree- @math boolean threshold functions, and answers an open question of (FOCS 2009).