Argimiro Arratia, Carlos E. Ortiz

We formulate a formal syntax of approximate formulas for the logic with counting

quantifiers, $\mathcal{SOLP}$, studied by us in \cite{aaco06}, where we showed the

following facts:

$(i)$ In the presence of a built--in (linear) order, $\mathcal{SOLP}$ can

describe {\bf NP}--complete problems and fragments of it capture classes like

{\bf P} ...
more >>>

Albert Atserias, Elitza Maneva

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 >>>