Complexity measures of sign matrices
DOI10.1007/S00493-007-2160-5zbMATH Open1164.68006OpenAlexW2006822886MaRDI QIDQ949752FDOQ949752
Adi Shraibman, Nathan Linial, Shahar Mendelson, Gideon Schechtman
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
Recommendations
- Complexity of matrix problems
- Computing the sign or the value of the determinant of an integer matrix, a complexity survey.
- Complexity metric and structural measure on the class of deterministic matrices
- Identifying complexity by means of matrices
- Complexity metric and structural measure on the class of non deterministic matrices
- On the Gröbner complexity of matrices
- scientific article; zbMATH DE number 2104735
- The complexity of computing the sign of the Tutte polynomial
- Complexity of Computations with Matrices and Polynomials
- scientific article; zbMATH DE number 810046
Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Local theory of Banach spaces (46B07) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Ramanujan graphs
- Concentration of measure and isoperimetric inequalities in product spaces
- A remark on matrix rigidity
- Title not available (Why is that?)
- Improved lower bounds on the rigidity of Hadamard matrices
- On the second eigenvalue of a graph
- Probabilistic communication complexity
- On the singularity probability of random Bernoulli matrices
- On the Probability That a Random ± 1-Matrix Is Singular
- Title not available (Why is that?)
- On rank vs. communication complexity
- Some combinatorial-algebraic problems from complexity theory
- Title not available (Why is that?)
- An algorithmic theory of learning: Robust concepts and random projection
- A proof of alon's second eigenvalue conjecture
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (31)
- The Communication Complexity of Non-signaling Distributions
- The hardest halfspace
- Complexity metric and structural measure on the class of deterministic matrices
- Identifying complexity by means of matrices
- The Hilbertian tensor norm and entangled two-prover games
- Knowledge Graph Completion via Complex Tensor Factorization
- Spectral gap in random bipartite biregular graphs and applications
- Upper bounds on communication in terms of approximate rank
- Learning Complexity vs Communication Complexity
- Matrix completion via max-norm constrained optimization
- Grothendieck-type inequalities in combinatorial optimization
- Lipschitz representations of subsets of the cube
- Kolmogorov width and approximate rank
- Max-norm optimization for robust matrix recovery
- Classical versus quantum communication in XOR games
- Positive semidefinite rank
- Deterministic Tensor Completion with Hypergraph Expanders
- Sign rank vs discrepancy
- Communication and information complexity
- A strong direct product theorem for quantum query complexity
- A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
- Minimum (maximum) rank of sign pattern tensors and sign nonsingular tensors
- A Borsuk-Ulam lower bound for sign-rank and its applications
- Upper bounds on communication in terms of approximate rank
- Lower bounds in communication complexity based on factorization norms
- Large violation of Bell inequalities with low entanglement
- The corruption bound, log-rank, and communication complexity
- An Additive Combinatorics Approach Relating Rank to Communication Complexity
- TIGHTER BOUNDS FOR THE DISCREPANCY OF BOXES AND POLYTOPES
- Approximate nonnegative rank is equivalent to the smooth rectangle bound
- Sign patterns with minimum rank 2 and upper bounds on minimum ranks
This page was built for publication: Complexity measures of sign matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q949752)
