Let Φ∈Rm x n be a sparse Johnson-Lindenstrauss transform [52] with column sparsity s. For a subset T of the unit sphere and ε∈(0,1/2), we study settings for m,s to ensure EΦ supx∈ T |Φ x|22 - 1| < ε, i.e. so that Φ preserves the norm of every x ∈ T simultaneously and multiplicatively up to 1+ε. We introduce a new complexity parameter, which depends on the geometry of T, and show that it suffices to choose s and m such that this parameter is small. Our result is a sparse analog of Gordon's theorem, which was concerned with a dense Φ having i.i.d. Gaussian entries. We qualitatively unify several results related to the Johnson-Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson-Lindenstrauss transform in randomized linear algebra, compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.

This work presents an explicit construction of a family of monotone expanders, which are bi-partite expander graphs whose edge-set is defined by (partial) monotone functions. The family is essentially defined by the Mobius action of SL2(R), the group of 2 x 2 matrices with determinant one, on the interval [0,1]. No other proof-of-existence for monotone expanders is known, not even using the probabilistic method.

We consider the problem of recovering a hidden element $s$ of a finite field $\mathbb{F}_q$ of $q$ elements from queries to an oracle that for a given $x \in \mathbb{F}_q$ returns $(x+s)^e$ for a given divisor $e \mid q-1$. We use some techniques from additive combinatorics and analytic number theory that lead to more efficient algorithms than the naive interpolation algorithm; for example, they use substantially fewer queries to the oracle.

We give a new explicit construction of n x N matrices satisfying the Restricted Isometry Property (RIP). Namely, for some e>0, large k and k2-e ≤ N ≤ k2+e, we construct RIP matrices of order k with n=O(k2-e). This overcomes the natural barrier n >> k2 for proofs based on small coherence, which are used in all previous explicit constructions of RIP matrices. Key ingredients in our proof are new estimates for sumsets in product sets and for exponential sums with the products of sets possessing special additive structure.

Goresky and Klapper conjectured that for any prime $p>13$ and any $\ell$-sequence ${\bf a}$ based on p, every pair of allowable decimations of ${\bf a}$ is cyclically distinct. The conjecture is essentially equivalent to the statement that the mapping $x\to Ax^d$, with $(d,p-1)=1$, $p\nmid A$, is a permutation of the even residues $\!\pmod p$ if and only if $d=1$ and $A\equiv1\pmod p$ for $p>13$. We prove the conjecture for $p>2.26\cdot10^{55}$ and establish it in a number of other special cases such as when $-.000274p