We give quantitative bounds on the sparsity of a real polynomial with non-negative coefficients vanishing on a slice of the Boolean cube $\{\pm1\}^n$. We obtain similar bounds on the dimension of real orthogonal representations of (the complement of) Johnson-type graphs. The estimates are related to the classical problem about ... more >>>

The quantum analogue of the PCP theorem for QMA remains wide open. A central obstacle is the local indistinguishability of quantum codes: every sufficiently small view of an encoded witness is independent of the witness, seemingly preventing a local verifier from distinguishing YES from NO instances. One approach to this ... more >>>

For a prime $p\geq 3$, a somewhat restricted $3$-AP in $\mathbb{F}_p^n$ is a triplet $(x,x+a,x+2a)$, where $x\in\mathbb{F}_p^n$ and $a\in \{0,1,2\}^n$. We prove a counting lemma for somewhat restricted $3$-APs in dense sets in $\mathbb{F}_p^n$. More precisely, we prove that for all $\alpha>0$, there exists $\beta>0$, such that for sufficiently large ... more >>>