Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorFriesen, Mirjamen
dc.contributor.authorHamed, Ayaen
dc.contributor.authorLee, Troyen
dc.contributor.authorOliver Theis, Dirken
dc.identifier.citationFriesen, M., Hamed, A., Lee, T., & Oliver Theis, D. (2015). Fooling-sets and rank. European journal of combinatorics, in press.en
dc.description.abstractAn 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.en
dc.format.extent11 p.en
dc.relation.ispartofseriesEuropean journal of combinatoricsen
dc.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:].en
dc.subjectDRNTU::Science::Mathematics::Discrete mathematics::Combinatoricsen
dc.titleFooling-sets and ranken
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen
dc.description.versionAccepted versionen
item.fulltextWith 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 Mar 18, 2023

Web of ScienceTM
Citations 50

Updated on Mar 17, 2023

Page view(s) 50

Updated on Mar 24, 2023

Download(s) 20

Updated on Mar 24, 2023

Google ScholarTM




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