From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces
From MaRDI portal
Publication:4994986
DOI10.1137/19M1299128MaRDI QIDQ4994986
Shiteng Chen, Xiaoming Sun, Youming Qiao, Ji Guan, Xiaohui Bei
Publication date: 22 June 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.03950
independent setvertex coloringexact exponential algorithmsisotropic spacealternating matrix spacesisotropic decomposition
Symbolic computation and algebraic computation (68W30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items (6)
Connections between graphs and matrix spaces ⋮ Groups, Graphs, and Hypergraphs: Average Sizes of Kernels of Generic Matrices with Support Constraints ⋮ Group-theoretic generalisations of vertex and edge connectivities ⋮ 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 ⋮ Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective
Cites Work
- Optimal algorithms of Gram-Schmidt type
- A fast isomorphism test for groups whose Lie algebra has genus 2
- Polynomial degree bounds for matrix semi-invariants
- Rank properties of subspaces of symmetric and Hermitian matrices over finite fields
- Decompositions of algebras over \(\mathbb{R}\) and \(\mathbb{C}\)
- Enumerating maximal independent sets with applications to graph colouring.
- Pairs of alternating forms and products of two skew-symmetric matrices
- On computing the determinant in small parallel time using a small number of processors
- Alternating forms and self-adjoint operators
- Spinor groups and algebraic coding theory
- Exact algorithms for exact satisfiability and number of perfect matchings
- A note on spaces of symmetric matrices
- Decomposing \(p\)-groups via Jordan algebras.
- On the dimension of spaces of linear transformations satisfying rank conditions
- Isotropic subspaces for skewforms and maximal abelian subgroups of \(p\)-groups
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- On generating all maximal independent sets
- Finite groups with modular lattice of centralizers
- Moduli and classification of irregular Kaehler manifolds (and algebraic varieties) with Albanese general type fibrations. Appendix by Arnaud Beauville
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- Paare alternierender Formen
- A note on the complexity of the chromatic number problem
- The number of generators and orders of Abelian subgroups of finite \(p\)-groups
- On symmetric degeneracy loci, spaces of symmetric matrices of constant rank and dual varieties
- The computational complexity of some problems of linear algebra
- Linear spaces of real matrices of constant rank
- Constructive non-commutative rank computation is in deterministic polynomial time
- Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling
- Decomposition of quantum Markov chains and its applications
- Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
- Classical complexity and quantum entanglement
- Generalized Wong sequences and their applications to Edmonds' problems
- Hilbert's Nullstellensatz is in the polynomial hierarchy
- Non-commutative Edmonds' problem and matrix semi-invariants
- Linear spaces of matrices of constant rank and instanton bundles
- Quantum stochastic processes. II
- Computing the structure of finite algebras
- Polynomial bounds for rings of invariants
- Geometric complexity theory V: Efficient algorithms for Noether normalization
- Large affine spaces of non-singular matrices
- Isomorphism in expanding families of indistinguishable groups
- Maximal Independent Sets and Separating Covers
- Onk-spaces of real matrices
- Primitivity testing of finite nilpotent linear groups
- Finding central decompositions of p-groups
- Set Partitioning via Inclusion-Exclusion
- Spaces of matrices of fixed rank
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- 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
- A New Algorithm for Generating All the Maximal Independent Sets
- A Deterministic Method for Computing Splitting Elements in Simple Algebras over Q
- Small Maximal Independent Sets and Faster Exact Graph Coloring
- The number of subgroups with trivial unipotent radicals in finite groups of Lie type
- ON THE CONSTRUCTION OF THE FREE FIELD
- Isotropy index for the connected sum and the direct product of manifolds
- Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing
- COMPUTING JORDAN NORMAL FORMS EXACTLY FOR COMMUTING MATRICES IN POLYNOMIAL TIME
- Fast Zeta Transforms for Lattices with Few Irreducibles
- Quantum Markovian Subsystems: Invariance, Attractivity, and Control
- Polynomial-time theory of matrix groups
- Decompositions of Hilbert spaces, stability analysis and convergence probabilities for discrete-time quantum dynamical semigroups
- Deterministic equation solving over finite fields
- Large Abelian Subgroups of p-Groups
- A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
- Graph isomorphism in quasipolynomial time [extended abstract]
- Bipartite perfect matching is in quasi-NC
- Computing isometry groups of Hermitian maps
- On the nlog n isomorphism technique (A Preliminary Report)
- On Matrices Whose Real Linear Combinations are Nonsingular
- An Analysis of Some Graph Theoretical Cluster Techniques
- Maximal Abelian Subgroups of the Symmetric Groups
- Groups with Abelian Central Quotient Group
- The Factorization of Linear Graphs
- Derandomizing polynomial identity tests means proving circuit lower bounds
- On cliques in graphs
- Vector fields on spheres
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces
