License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.22
URN: urn:nbn:de:0030-drops-171445
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17144/
Hatami, Hamed ;
Hatami, Pooya ;
Pires, William ;
Tao, Ran ;
Zhao, Rosie
Lower Bound Methods for Sign-Rank and Their Limitations
Abstract
The sign-rank 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 sign-rank of explicit matrices: (i) Sign-rank is at least the VC-dimension; (ii) Forster’s method, which states that sign-rank is at least the inverse of the largest possible average margin among the representations of the matrix by points and half-spaces; (iii) Sign-rank 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 super-constant lower bound for the sign-rank of a matrix, then the other two methods will fail as well.
- We show that there exist n × n matrices with sign-rank n^Ω(1) for which none of these methods can provide a super-constant lower bound.
- We show that sign-rank 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., xor-lifts), sign-rank 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 sign-rank and discrepancy, we conjecture that sign-ranks 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 Sign-Rank and Their Limitations}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {22:1--22:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-249-5},
ISSN = {1868-8969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17144},
URN = {urn:nbn:de:0030-drops-171445},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.22},
annote = {Keywords: Average Margin, Communication complexity, margin complexity, monochromatic rectangle, Sign-rank, Unbounded-error communication complexity, VC-dimension}
}
|
Keywords: |
|
Average Margin, Communication complexity, margin complexity, monochromatic rectangle, Sign-rank, Unbounded-error communication complexity, VC-dimension |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
15.09.2022 |
