6 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…

Odd Alternating Cycle Conjecture. For every field $\mathbb{F}$ there exist $\varepsilon>0$ and an odd integer $\ell$ such that every $n$-vertex directed graph $G$ with

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…

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…