A boolean function $f$ has Fourier dimension $k$ if its strings with nonzero Fourier coefficients span a subspace of dimension $k$. We first consider the property testing task of determining whether a function has Fourier dimension at most $k$, or is $\epsilon$-far from being so. We show that there is ... more >>>

We give fast algorithms for low-rank tensor decomposition.
Over $\mathbb R$ and $\mathbb C$ we give a deterministic algorithm that takes as input an order-$d$, width-$n$, rank-$k$ tensor, gets measurement access to the tensor, runs in time
$k^{O(k^2)}\cdot \mathrm{poly}(n,d)$, and finds a minimal decomposition as a sum of rank-one ... more >>>

The problem of decomposing an algebraic variety into more structured components (such as equidimensional, irreducible, or connected components) is a fundamental problem in computer algebra and algebraic geometry. In this work, we study the computational complexity of computing equidimensional components of algebraic varieties, represented via Chow forms.

We improve the ... more >>>