Complexity measures of sign matrices

Nati Linial; Shahar Mendelson; Gideon Schechtman; Adi Shraibman

doi:10.1007/s00493-007-2160-5

Complexity measures of sign matrices

Nati Linial^*, Shahar Mendelson, Gideon Schechtman, Adi Shraibman

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

102 Citations (Scopus)

Abstract

In this paper we consider four previously known parameters of sign matrices from a complexity-theoretic perspective. The main technical contributions are tight (or nearly tight) inequalities that we establish among these parameters. Several new open problems are raised as well.

Original language	English
Pages (from-to)	439-463
Number of pages	25
Journal	Combinatorica
Volume	27
Issue number	4
DOIs	https://doi.org/10.1007/s00493-007-2160-5
Publication status	Published - Jul 2007

Access to Document

10.1007/s00493-007-2160-5

Cite this

@article{937cac3da2b743a0b74791ed84d9672f,

title = "Complexity measures of sign matrices",

abstract = "In this paper we consider four previously known parameters of sign matrices from a complexity-theoretic perspective. The main technical contributions are tight (or nearly tight) inequalities that we establish among these parameters. Several new open problems are raised as well.",

author = "Nati Linial and Shahar Mendelson and Gideon Schechtman and Adi Shraibman",

year = "2007",

month = jul,

doi = "10.1007/s00493-007-2160-5",

language = "English",

volume = "27",

pages = "439--463",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "4",

}

TY - JOUR

T1 - Complexity measures of sign matrices

AU - Linial, Nati

AU - Mendelson, Shahar

AU - Schechtman, Gideon

AU - Shraibman, Adi

PY - 2007/7

Y1 - 2007/7

N2 - In this paper we consider four previously known parameters of sign matrices from a complexity-theoretic perspective. The main technical contributions are tight (or nearly tight) inequalities that we establish among these parameters. Several new open problems are raised as well.

AB - In this paper we consider four previously known parameters of sign matrices from a complexity-theoretic perspective. The main technical contributions are tight (or nearly tight) inequalities that we establish among these parameters. Several new open problems are raised as well.

UR - http://www.scopus.com/inward/record.url?scp=44449089397&partnerID=8YFLogxK

U2 - 10.1007/s00493-007-2160-5

DO - 10.1007/s00493-007-2160-5

M3 - Article

SN - 0209-9683

VL - 27

SP - 439

EP - 463

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -

Complexity measures of sign matrices

Abstract

Access to Document

Other files and links

Fingerprint

Cite this