17 citations · 34 across the 18 of their papers we have counts for
4 papers · 1 filter
On the Expressive Power of Homomorphism Counts
Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu
A classical result by Lovász asserts that two graphs and are isomorphic if and only if they have the same left profile, that is, for every graph , the number of homomorp…
On the Computational Complexity of Non-dictatorial Aggregation
Lefteris Kirousis, Phokion G. Kolaitis, John Livieratos
We investigate when non-dictatorial aggregation is possible from an algorithmic perspective, where non-dictatorial aggregation means that the votes cast by the members of a society…
Aggregation of Votes with Multiple Positions on Each Issue
Lefteris Kirousis, Phokion G. Kolaitis, John Livieratos
We consider the problem of aggregating votes cast by a society on a fixed set of issues, where each member of the society may vote for one of several positions on each issue, but t…
Random Graphs and the Parity Quantifier
Phokion G. Kolaitis, Swastik Kopparty
The classical zero-one law for first-order logic on random graphs says that for any first-order sentence in the theory of graphs, as n approaches infinity, the probability that…