Fooling-sets and rank

• Main Authors: Friesen, Mirjam, Hamed, Aya, Lee, Troy, Oliver Theis, Dirk
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2015
• 主題: DRNTU::Science::Mathematics::Discrete mathematics::Combinatorics
• 在線閱讀: https://hdl.handle.net/10356/107304; http://hdl.handle.net/10220/25431

An n x n matrixM is called a fooling-set matrix of size n if its diagonal entries are nonzero and Mk,l; Ml,k = 0 for every k ≠ l. Dietzfelbinger, Hromkovič, and Schnitger (1996) showed that n ≤ (rkM)2, regardless of over which field the rank is computed, and asked whether the exponent on rkM can be...