Article ID Journal Published Year Pages File Type
4653413 European Journal of Combinatorics 2015 11 Pages PDF
Abstract

An n×nn×n matrix MM is called a fooling-set matrix of size  nn if its diagonal entries are nonzero and Mk,ℓMℓ,k=0Mk,ℓMℓ,k=0 for every k≠ℓk≠ℓ. Dietzfelbinger, Hromkovič, and Schnitger (1996) showed that n≤(rkM)2n≤(rkM)2, regardless of over which field the rank is computed, and asked whether the exponent on rkMrkM can be improved.We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size n=(rkM+12). In nonzero characteristic, we construct an infinite family of matrices with n=(1+o(1))(rkM)2n=(1+o(1))(rkM)2.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,