Please use this identifier to cite or link to this item:
Title: Fooling-sets and rank
Authors: Friesen, Mirjam
Hamed, Aya
Lee, Troy
Oliver Theis, Dirk
Keywords: DRNTU::Science::Mathematics::Discrete mathematics::Combinatorics
Issue Date: 2015
Source: Friesen, M., Hamed, A., Lee, T., & Oliver Theis, D. (2015). Fooling-sets and rank. European journal of combinatorics, in press.
Series/Report no.: European journal of combinatorics
Abstract: 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 improved. We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size n = (rkM+1 2). In nonzero characteristic, we construct an infinite family of matrices with n = (1+o(1))(rkM)2.
ISSN: 0195-6698
DOI: 10.1016/j.ejc.2015.02.016
Schools: School of Physical and Mathematical Sciences 
Rights: © 2015 Elsevier Ltd. This is the author created version of a work that has been peer reviewed and accepted for publication by European Journal of Combinatorics, Elsevier Ltd. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [Article DOI:].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Fooling-sets and rank.pdf179.27 kBAdobe PDFThumbnail

Citations 50

Updated on Jun 16, 2024

Web of ScienceTM
Citations 50

Updated on Oct 27, 2023

Page view(s) 20

Updated on Jun 19, 2024

Download(s) 20

Updated on Jun 19, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.