Skip to main navigation Skip to search Skip to main content

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

    113 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 languageEnglish
    Pages (from-to)439-463
    Number of pages25
    JournalCombinatorica
    Volume27
    Issue number4
    DOIs
    Publication statusPublished - Jul 2007

    Fingerprint

    Dive into the research topics of 'Complexity measures of sign matrices'. Together they form a unique fingerprint.

    Cite this