Source author record

Aya Hamed

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity math.CO

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Fooling sets and rank

An $n\times n$ matrix $M$ is called a \textit{fooling-set matrix of size $n$ } if its diagonal entries are nonzero and $M_{k,\ell} M_{\ell,k} = 0$ for every $k\ne \ell$ . Dietzfelbinger, Hromkovi{č}, and Schnitger (1996) showed that $n \le (\mbox{rk} M)^2$, regardless of over which field the rank is computed, and asked whether the exponent on $\mbox{rk} M$ can be improved. We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size $n = \binom{\mbox{rk} M+1}{2}$. In nonzero characteristic, we construct an infinite family of matrices with $n= (1+o(1))(\mbox{rk} M)^2$.

preprint2013arXiv

Rank and fooling set size

Say that A is a Hadamard factorization of the identity I_n of size n if the entrywise product of A and the transpose of A is I_n. It can be easily seen that the rank of any Hadamard factorization of the identity must be at least sqrt{n}. Dietzfelbinger et al. raised the question if this bound can be achieved, and showed a boolean Hadamard factorization of the identity of rank n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard factorization of the identity A of size r(r-1)+1 and rank r over F_p. Here we resolve the question for fields of zero characteristic, up to a constant factor, giving a construction of Hadamard factorizations of the identity of rank r and size (r+1)r/2. The matrices in our construction are blockwise Toeplitz, and have entries whose magnitudes are binomial coefficients.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.