Fooling-sets and rank

• المؤلفون الرئيسيون: Friesen, Mirjam, Hamed, Aya, Lee, Troy, Oliver Theis, Dirk
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: 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...