5 problems

Let $M\in\mathbb F_2^{m\times k}$ and $\sigma\in\\{0,1\\}^k$. A function $f:\mathbb F_2^n\to\\{0,1\\}$ is $(M,\sigma)$-free if there is no $k$-tuple of row vectors…

Let a nontrivial monotone property be characterized by freeness from solutions to a finite family of equations; according to the surrounding discussion, such a property is equivale…

Let a monotone property of Boolean functions be characterized by freeness from solutions to a family $\mathcal{F}$ of equations. The query complexity of testing such properties is…

Let $f$ and $g$ be Boolean functions on a common vector-space domain. Say that they are isomorphic up to linear transformations of the variables if there is an invertible linear tr…

Let $f$ be a Boolean function, and let a system of linear equations specify a collection of linear constraints on points in its domain. A property is linear-invariant if it is pres…