Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/107304
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.
URI: https://hdl.handle.net/10356/107304
http://hdl.handle.net/10220/25431
ISSN: 0195-6698
DOI: 10.1016/j.ejc.2015.02.016
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: http://dx.doi.org/10.1016/j.ejc.2015.02.016].
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
View/Open

SCOPUSTM   
Citations 50

4
Updated on Jan 25, 2023

Web of ScienceTM
Citations 50

4
Updated on Jan 26, 2023

Page view(s) 50

551
Updated on Jan 29, 2023

Download(s) 20

189
Updated on Jan 29, 2023

Google ScholarTM

Check

Altmetric


Plumx

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