We consider the problem of representing Boolean functions exactly by" sparse" linear
combinations (over $\mathbb {R} $) of functions from some" simple" class ${\cal C} $. In …

We use tools of additive combinatorics for the study of subvarieties defined by high rank
families of polynomials in high dimensional F _q F q-vector spaces. In the first, analytic part …

We consider the problem of decoding corrupted error correcting codes with NC $^ 0 [\oplus]
$ circuits in the classical and quantum settings. We show that any such classical circuit can …

We establish a link between stabilizer states, stabilizer rank, and higher-order Fourier
analysis–a still-developing area of mathematics that grew out of Gowers's celebrated Fourier …

In this paper, we give a cubic Goldreich-Levin algorithm which makes polynomially-many
queries to a function f: 𝔽 np→ ℂ and produces a decomposition of f as a sum of cubic …

The approximate stabilizer rank of a quantum state is the minimum number of terms in any
approximate decomposition of that state into stabilizer states. Bravyi and Gosset showed that …

The nonlinear interactions between river discharge, astronomical tidal wave, and local
geomorphology during storm passage or water release from upstream dams can produce …

We study the property testing of functions \mathbbF_p^n→R for fixed prime p and positive
integer R. We work in the natural model where we are allowed to query the function on a …

The (low soundness) linearity testing problem for the middle slice of the Boolean cube is as
follows. Let $\varepsilon> 0$ and $ f $ be a function on the middle slice on the Boolean …

Two Boolean functions f, g: F_2^{n}\to {-1, 1} are called linearly isomorphic if there exists an
invertible matrix M\in F_2^{n\times n} such that f\circ M= g. Testing linear isomorphism is a …