On the expressive power of linear algebra on graphs

DOI10.1007/s00224-020-09990-9zbMath1466.05118arXiv1812.04379OpenAlexW3091502386MaRDI QIDQ2035472

Floris Geerts

Publication date: 24 June 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

query languageslinear algebra

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Basic linear algebra (15A99)

Related Items (2)

MATLANG ⋮ On the expressive power of message-passing neural networks as global feature map transformers

Uses Software

• MathOverflow
• LaraDB

Cites Work

• 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
• Spectra of graphs
• Finding and counting given length cycles
• Elements of finite model theory.
• The spectral approach to determining the number of walks in a graph
• Cospectral graphs and the generalized adjacency matrix
• Coherent algebras and the graph isomorphism problem
• On the power of combinatorial and spectral invariants
• Graph isomorphism and theorems of Birkhoff type
• A note on cospectral graphs
• A note on compact graphs
• An optimal lower bound on the number of variables for graph identification
• Fractional isomorphism of graphs
• Expressive power of SQL.
• Which graphs are determined by their spectrum?
• Enumeration of cospectral graphs.
• Logical hierarchies in PTIME
• Descriptive complexity of graph spectra
• Sherali-Adams relaxations of graph isomorphism polytopes
• Unitary and orthogonal equivalence of sets of matrices
• Algebra I
• Sherali--Adams Relaxations and Indistinguishability in Counting Logics
• Dimension Reduction via Colour Refinement
• Linear Algebra Done Right
• Pebble Games with Algebraic Rules
• On the Expressive Power of Query Languages for Matrices
• PEBBLE GAMES AND LINEAR EQUATIONS
• On the Descriptive Complexity of Linear Algebra
• Lov\'asz Meets Weisfeiler and Leman
• On the Combinatorial Power of the Weisfeiler-Lehman Algorithm
• Rank logic is dead, long live rank logic!
• Logics with aggregate operators
• The semigroup of doubly-stochastic matrices
• When Can Matrix Query Languages Discern Matrices
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• On matrices and \(K\)-relations

This page was built for publication: On the expressive power of linear algebra on graphs