Fooling-sets and rank

• Main Authors: Friesen, Mirjam, Hamed, Aya, Lee, Troy, Oliver Theis, Dirk
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2015
• Subjects: DRNTU::Science::Mathematics::Discrete mathematics::Combinatorics
• Online Access: https://hdl.handle.net/10356/107304; http://hdl.handle.net/10220/25431
• Institution: Nanyang Technological University

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...