We consider the problem of testing if an unknown low-degree polynomial p over ℝn is sparse versus far from sparse, given access to noisy evaluations of the polynomial p at randomly chosen points. This is a natural property-testing version of various well-studied problems about learning low-degree sparse polynomials in the presence of noise, and is a generalization of the work of Chen, De, and Servedio (2020), on testing noisy linear functions for sparsity, to the more challenging setting of low-degree polynomials.

We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwise distances. The novelty is studying average-distortion: for any fixed (yet, arbitrary) distribution $\mu$ over the metric, the sketch should not over-estimate distances, and it should (approximately) preserve the average distance with respect to draws from $\mu$. The notion generalizes average-distortion embeddings into $\ell_{1}$ [1], [2] as well as data-dependent locality-sensitive hashing [3], [4], which have been recently studied in the context of nearest neighbor search.•For all $p \in(2, \infty)$ and any c larger than a fixed constant, we give an average-distortion sketch for ($[\Delta]^{d}, \ell_{p}$) with approximation c and bit-complexity poly $\left(2^{p / c} \cdot \log (d \Delta)\right)$, which is provably impossible in (worst-case) sketching.•As an application, we improve on the approximation of sublinear-time data structures for nearest neighbor search over $\ell_{p}$ (for large $p\gt2$). The prior best approximation was $O(p)$ [2], [4], and we show it can be any c larger than a fixed constant (irrespective of p) by using $n^{O(p / c)}$ space.We give some evidence that $2^{\Omega(p / c)}$ space may be necessary by giving a lower bound on average-distortion sketches which produce a certain probabilistic certificate of farness (which our sketches crucially rely on).

We present the first polynomial-time approximation scheme (PTAS) for the stochastic knapsack problem that does not relax the knapsack’s capacity. Given n items with known arbitrary independent size distributions and fixed profits, an accuracy parameter $\varepsilon \in(0,1)$, and an overflow probability bound $\alpha$, our algorithm computes a set of items with profit at least $(1-\varepsilon)$ times optimal, while ensuring the probability of exceeding the capacity is at most $4 \sqrt{\alpha}+\varepsilon$. Prior to our work, no PTAS was known without either allowing a ($1+\varepsilon$) capacity expansion or restricting to special distribution classes (such as Poisson or Gaussian). A key tool in our algorithm is an anti-concentration result that allows us to handle “low-profit” items by adapting a known PTAS result for the case when we are allowed to expand knapsack capacity by a ($1+\varepsilon$) factor. We then show that we are able to convert this solution into another solution with a similar profit which strictly obeys the knapsack capacity, but requires that we relax the overflow probability to a $4 \sqrt{\alpha}+\varepsilon$ factor. In the special case where the item sizes are scaled Bernoulli random variables (which have support on 0 and exactly one other value), we extend our approach to obtain an improved overflow probability guarantee of $\alpha+\varepsilon$. We make this improvement by exploiting the fact that these random variables are defined by only two parameters (the probability of being non-zero and the non-zero value in the support), which allows us to avoid some of the complexity and overhead of our algorithm for arbitrary distributions.

We present a parallel algorithm for the (1 — ɛ) -approximate maximum flow problem in capacitated, undirected graphs with n vertices and m edges, achieving O(ɛ-3 polylog n) depth and O(mɛ-3 polylog n) work in the PRAM model. Although near-linear time sequential algorithms for this problem have been known for almost a decade, no parallel algorithms that simultaneously achieved polylogarithmic depth and near-linear work were known.