10 citations · 37 across the 29 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.LO2016
Bounded degree and planar spectra
Anuj Dawar, Eryk Kopczyński
The finite spectrum of a first-order sentence is the set of positive integers that are the sizes of its models. The class of finite spectra is known to be the same as the complexit…
cs.LO2016★ 1 cited
Descriptive complexity of graph spectra
Anuj Dawar, Simone Severini, Octavio Zapata
Two graphs are co-spectral if their respective adjacency matrices have the same multi-set of eigenvalues. A graph is said to be determined by its spectrum if all graphs that are co…
cs.LO2016★ 1 cited
Lasserre Lower Bounds and Definability of Semidefinite Programming
Anuj Dawar, Pengming Wang
For a large class of optimization problems, namely those that can be expressed as finite-valued constraint satisfaction problems (VCSPs), we establish a dichotomy on the number of…