Complexity measures of sign matrices

DOI10.1007/s00493-007-2160-5zbMath1164.68006OpenAlexW2006822886MaRDI QIDQ949752

Adi Shraibman, Shahar Mendelson, Gideon Schechtman, Nathan Linial

Publication date: 21 October 2008

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-007-2160-5

zbMATH Keywords

sign matrixcomplexity measure

Mathematics Subject Classification ID

Computational learning theory (68Q32) Local theory of Banach spaces (46B07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Spectral gap in random bipartite biregular graphs and applications, The corruption bound, log-rank, and communication complexity, Grothendieck-Type Inequalities in Combinatorial Optimization, Matrix completion via max-norm constrained optimization, The Communication Complexity of Non-signaling Distributions, Classical versus quantum communication in XOR games, A strong direct product theorem for quantum query complexity, Approximate nonnegative rank is equivalent to the smooth rectangle bound, Kolmogorov width and approximate rank, Communication and information complexity, TIGHTER BOUNDS FOR THE DISCREPANCY OF BOXES AND POLYTOPES, A generalized Grothendieck inequality and nonlocal correlations that require high entanglement, The Hilbertian tensor norm and entangled two-prover games, Minimum (maximum) rank of sign pattern tensors and sign nonsingular tensors, Learning Complexity vs Communication Complexity, The hardest halfspace, Max-norm optimization for robust matrix recovery, Deterministic Tensor Completion with Hypergraph Expanders, Large violation of Bell inequalities with low entanglement, Positive semidefinite rank, Sign rank vs discrepancy, Lower bounds in communication complexity based on factorization norms, Knowledge Graph Completion via Complex Tensor Factorization, An Additive Combinatorics Approach Relating Rank to Communication Complexity, Sign patterns with minimum rank 2 and upper bounds on minimum ranks, Lipschitz representations of subsets of the cube, Upper bounds on communication in terms of approximate rank

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A remark on matrix rigidity
• Probabilistic communication complexity
• Ramanujan graphs
• On the second eigenvalue of a graph
• Improved lower bounds on the rigidity of Hadamard matrices
• Some combinatorial-algebraic problems from complexity theory
• On rank vs. communication complexity
• Concentration of measure and isoperimetric inequalities in product spaces
• An algorithmic theory of learning: Robust concepts and random projection
• On the singularity probability of random Bernoulli matrices
• A proof of alon's second eigenvalue conjecture
• On the Probability That a Random ± 1-Matrix Is Singular