Complexity measures of sign matrices
type: Item
instance of: scholarly article
title: Complexity measures of sign matrices
zbMATH Open document ID: 1164.68006
author: Shahar Mendelson
author: Gideon Schechtman
author: Adi Shraibman
author: Nathan Linial
published in: Combinatorica
publication date: 2008-10-21T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 46B07
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q32
zbMATH DE Number: 5355064
zbMATH Keywords: sign matrix
zbMATH Keywords: complexity measure
MaRDI profile type: Publication
full work available at URL: s00493-007-2160-5
OpenAlex ID: W2006822886
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: An algorithmic theory of learning: Robust concepts and random projection
cites work: Q4781229
cites work: Q5690490
cites work: Q4474216
cites work: Q4781230
cites work: A proof of alon's second eigenvalue conjecture
cites work: On the Probability That a Random ± 1-Matrix Is Singular
cites work: Improved lower bounds on the rigidity of Hadamard matrices
cites work: Q4231904
cites work: Ramanujan graphs
cites work: On the second eigenvalue of a graph
cites work: On rank vs. communication complexity
cites work: Probabilistic communication complexity
cites work: Q3715635
cites work: Some combinatorial-algebraic problems from complexity theory
cites work: A remark on matrix rigidity
cites work: Concentration of measure and isoperimetric inequalities in product spaces
cites work: On the singularity probability of random Bernoulli matrices
cites work: Q4041061
DOI: 10.1007/S00493-007-2160-5
Recommended article: Complexity of matrix problems
Recommended article: Computing the sign or the value of the determinant of an integer matrix, a complexity survey.
Recommended article: Q3519845
Recommended article: Identifying complexity by means of matrices
Recommended article: Q3633751
Recommended article: On the Gröbner complexity of matrices
Recommended article: Q4820785
Recommended article: The Complexity of Computing the Sign of the Tutte Polynomial
Recommended article: Complexity of Computations with Matrices and Polynomials
Recommended article: Q4853275
description: scientific article; zbMATH DE number 5355064