The sign-rank of a matrix $A$ with $\pm 1$ entries is the smallest rank of a real matrix with the same sign pattern as $A$. To the best of our knowledge, there are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is ... more >>>

The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm of $f$. Green and Sanders' quantitative version of Cohen's idempotent theorem states that if the spectral norm of $f:\mathbb{F}_2^n \to \{0,1\}$ is at most $M$, then the support of ... more >>>