Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SHERALI-ADAMS RELAXATIONS:
Reports tagged with Sherali-Adams relaxations:
TR11-077 | 8th May 2011
Albert Atserias, Elitza Maneva

Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics

Two graphs with adjacency matrices \mathbf{A} and \mathbf{B} are isomorphic if there exists a permutation matrix \mathbf{P} for which the identity \mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B} holds. Multiplying through by \mathbf{P} and relaxing the permutation matrix to a doubly stochastic matrix leads to the notion of fractional isomorphism. We show ... more >>>




ISSN 1433-8092 | Imprint