8 problems

A Hadamard matrix is a square matrix whose entries are $+1$ and $-1$ and whose rows are mutually orthogonal. A matrix is strictly Valiant-rigid when its strict rigidity does not ad…

Let $H^k\in\{-1,1\}^{n\times n}$ be Walsh–Hadamard matrices, where $n=2^k$. A matrix is Valiant-rigid if it cannot be changed in too few entries to obtain a matrix of substantially…

Let $p$ be a prime, let $G=SL_2(\mathbb{F}_p)$, and let $f:G\rightarrow\{0,1\}$ be chosen uniformly at random. Write $M_G(f)$ for the corresponding $G$-circulant matrix. Rigidity c…

Let $\operatorname{LS}_n(r,s)$ denote the set of matrices that can be written as the sum of an $n\times n$ matrix of rank at most $r$ and an $n\times n$ matrix with at most $s$ non…

Let $\mathbb{F}$ be a field. A digraph is an alternating odd cycle if its underlying undirected graph is a cycle and the orientations of its edges alternate with one exception. For…

Fix $0<\epsilon<1$ and $0<\delta<1$. Set $r=\epsilon n$ and $s=n^{1+\delta}$. The notation $\hat{\mathcal R}[n,r,s]$ denotes the relevant matrix rigidity variety, and its irreducib…

Let $M$ be an $n \times n$ real matrix with $\operatorname{rank}(M)=r$ and such that $M_{i,j} \ne 0$ for at most $\varepsilon n^2$ entries. A large zero rectangle conjecture assert…

Dvir's conjecture. Such a locally correctable code cannot have dimension $0.99\cdot n$.