Abstract
The signrank of a matrix A with ±1 entries is the smallest rank of a real matrix with the same sign pattern as A. To the best of our knowledge, there are only three known methods for proving lower bounds on the signrank of explicit matrices: (i) Signrank is at least the VCdimension; (ii) Forster’s method, which states that signrank is at least the inverse of the largest possible average margin among the representations of the matrix by points and halfspaces; (iii) Signrank is at least a logarithmic function of the density of the largest monochromatic rectangle.
We prove several results regarding the limitations of these methods.
 We prove that, qualitatively, the monochromatic rectangle density is the strongest of these three lower bounds. If it fails to provide a superconstant lower bound for the signrank of a matrix, then the other two methods will fail as well.
 We show that there exist n × n matrices with signrank n^Ω(1) for which none of these methods can provide a superconstant lower bound.
 We show that signrank is at most an exponential function of the deterministic communication complexity with access to an equality oracle. We combine this result with Green and Sanders' quantitative version of Cohen’s idempotent theorem to show that for a large class of sign matrices (e.g., xorlifts), signrank is at most an exponential function of the γ₂ norm of the matrix. We conjecture that this holds for all sign matrices.
 Towards answering a question of Linial, Mendelson, Schechtman, and Shraibman regarding the relation between signrank and discrepancy, we conjecture that signranks of the ±1 adjacency matrices of hypercube graphs can be arbitrarily large. We prove that none of the three lower bound techniques can resolve this conjecture in the affirmative.
BibTeX  Entry
@InProceedings{hatami_et_al:LIPIcs.APPROX/RANDOM.2022.22,
author = {Hatami, Hamed and Hatami, Pooya and Pires, William and Tao, Ran and Zhao, Rosie},
title = {{Lower Bound Methods for SignRank and Their Limitations}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {22:122:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17144},
URN = {urn:nbn:de:0030drops171445},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.22},
annote = {Keywords: Average Margin, Communication complexity, margin complexity, monochromatic rectangle, Signrank, Unboundederror communication complexity, VCdimension}
}
Keywords: 

Average Margin, Communication complexity, margin complexity, monochromatic rectangle, Signrank, Unboundederror communication complexity, VCdimension 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) 
Issue Date: 

2022 
Date of publication: 

15.09.2022 