Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

We give efficient algorithms for finding powersum decomposition of an input polynomial with component s. The case of linear s is equivalent to the wellstudied tensor decomposition problem while the quadratic case occurs naturally in studying identifiability of nonspherical Gaussian mixtures from loworder moments. Unlike tensor decomposition, both the unique identifiability and algorithms for this problem are not wellunderstood. For the simplest setting of quadratic s and , prior work of [GHK15] yields an algorithm only when . On the other hand, the more general recent result of [GKS20] builds an algebraic approach to handle any components but only when is large enough (while yielding no bounds for or even ) and only handles an inverse exponential noise. Our results obtain a substantial quantitative improvement on both the prior works above even in the base case of and quadratic s. Specifically, our algorithm succeeds in decomposing a sum of generic quadratic s for and more generally the th powersum of generic degree polynomials for any . Our algorithm relies only on basic numerical linear algebraic primitives, is exact (i.e., obtain arbitrarily tiny error up to numerical precision), and handles an inverse polynomial noise when the s have random Gaussian coefficients.Free, publiclyaccessible full text available October 1, 2023

Free, publiclyaccessible full text available June 9, 2023

Higher order random walks (HDwalks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass (ITCS 2016), yet their broader combinatorial and spectral properties remain poorly understood. We develop a combinatorial characterization of the spectral structure of HDwalks on twosided localspectral expanders (Dinur and Kaufman FOCS 2017), which offer a broad generalization of the wellstudied Johnson and Grassmann graphs. Our characterization, which shows that the spectra of HDwalks lie tightly concentrated in a few combinatorially structured strips, leads to novel structural theorems such as a tight ℓ2characterization of edgeexpansion, as well as to a new understanding of localtoglobal graph algorithms on HDX. Towards the latter, we introduce a novel spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank as a parameter controlling the performance of algorithms on structured objects. Combined with a sumofsquares proof for the former ℓ2characterization, we give a concrete application of this framework to algorithms for unique games on HDwalks, where in many cases we improve the state of the art (Barak, Raghavendra, and Steurer FOCS 2011, and Arora, Barak, and Steurer JACM 2015) from nearlyexponential tomore »

We give a new algorithm for approximating the Discrete Fourier transform of an approximately sparse signal that has been corrupted by worstcase L0 noise, namely a bounded number of coordinates of the signal have been corrupted arbitrarily. Our techniques generalize to a wide range of linear transformations that are used in data analysis such as the Discrete Cosine and Sine transforms, the Hadamard transform, and their highdimensional analogs. We use our algorithm to successfully defend against well known L0 adversaries in the setting of image classification. We give experimental results on the Jacobianbased Saliency Map Attack (JSMA) and the Carlini Wagner (CW) L0 attack on the MNIST and FashionMNIST datasets as well as the Adversarial Patch on the ImageNet dataset.

We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples X1, X2, . . . and Y1, Y2, . . . with the pairs (X1, Y1), (X2, Y2), . . . being drawn independently from some known probability distribution μ. They wish to communicate so as to agree on L bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions μ = μr,n,L, parametrized by integers r, n and L, such that for every r there exists a constant b = b(r) for which CRG (respectively SKG) is feasible when (Xi, Yi) ~ μr,n,L with r + 1 rounds of communication, each consisting of O(log n) bits, butmore »