Connections between graphs and matrix spaces

DOI10.1007/s11856-023-2515-7zbMath1522.05281arXiv2206.04815OpenAlexW4387382674MaRDI QIDQ6074039

Youming Qiao, Chuanqi Zhang, Avi Wigderson, Yinan Li, Yuval Wigderson

Publication date: 12 October 2023

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2206.04815

zbMATH Keywords

acyclicityirreducibilitynilpotencystrong connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Algebraic systems of matrices (15A30) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Related Items (1)

Maximal generalized rank in graphical matrix spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expansion in SL\(_2(\mathbb R)\) and monotone expanders
• On Gerstenhaber's theorem for spaces of nilpotent matrices over a skew field
• Nilpotent linear spaces and Albert's problem
• Towards dimension expanders over finite fields
• Linear spaces of nilpotent matrices
• On computing the determinant in small parallel time using a small number of processors
• Expanders and dimensional expansion
• Blockers and transversals
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• Vector spaces of matrices of low rank
• Rubber bands, convex embeddings and graph connectivity
• The computational complexity of some problems of linear algebra
• Constructive non-commutative rank computation is in deterministic polynomial time
• Wildness for tensors
• The Schur complement and its applications
• Classical complexity and quantum entanglement
• On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
• Enumerating alternating matrix spaces over finite fields with explicit coordinates
• Quantum graphs as quantum relations
• Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
• Connectivity for quantum graphs
• Operator scaling: theory and applications
• Lovász theta type norms and operator systems
• Generalized Wong sequences and their applications to Edmonds' problems
• Non-commutative Edmonds' problem and matrix semi-invariants
• On the dimension of linear spaces of nilpotent matrices
• Dimension expanders
• Quantum expanders and geometry of operator spaces
• Sur une généralisation du groupe orthogonal à quatre variables
• Graph Theory
• Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
• Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number
• Arithmetic Circuits: A survey of recent results and open questions
• On Nilalgebras and Linear Varieties of Nilpotent Matrices, I
• On Spaces of Linear Transformations with Bounded Rank
• Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization
• ON THE MAXIMAL RANK IN A SUBSPACE OF MATRICES
• Matrix Analysis
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Singular spaces of matrices and their application in combinatorics
• The word problem for free fields: a correction and an addendum
• Spectral Properties of Positive Maps on C^* -Algebras
• Spaces of Matrices with Several Zero Eigenvalues
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces
• Bipartite Perfect Matching is in Quasi-NC
• Reducibility among Combinatorial Problems
• Group-theoretic generalisations of vertex and edge connectivities
• On the Weisfeiler-Leman Dimension of Finite Groups
• Deterministic Polynomial Time Algorithms for Matrix Completion Problems
• On Matrices Whose Real Linear Combinations are Nonsingular
• Systems of distinct representatives and linear algebra
• Groups with Abelian Central Quotient Group
• The Factorization of Linear Graphs
• A Theory of Power-Associative Commutative Algebras
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Vector fields on spheres
• Enumerating conjugacy classes of graphical groups over finite fields

This page was built for publication: Connections between graphs and matrix spaces