17 citations · 34 across the 18 of their papers we have counts for
23 papers
On the Expressive Power of Transformers
Phokion Kolaitis, Rik Sengupta
Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is…
When do homomorphism counts help in query algorithms?
Balder ten Cate, Víctor Dalmau, Phokion G. Kolaitis +1
A query algorithm based on homomorphism counts is a procedure for determining whether a given instance satisfies a property by counting homomorphisms between the given instance and…
A Framework for Combining Entity Resolution and Query Answering in Knowledge Bases
Ronald Fagin, Phokion G. Kolaitis, Domenico Lembo +2
We propose a new framework for combining entity resolution and query answering in knowledge bases (KBs) with tuple-generating dependencies (tgds) and equality-generating dependenci…
Multi-Structural Games and Beyond
Marco Carmosino, Ronald Fagin, Neil Immerman +3
Multi-structural (MS) games are combinatorial games that capture the number of quantifiers of first-order sentences. On the face of their definition, MS games differ from Ehrenfeuc…
Consistent Answers of Aggregation Queries using SAT Solvers
Akhil A. Dixit, Phokion G. Kolaitis
The framework of database repairs and consistent answers to queries is a principled approach to managing inconsistent databases. We describe the first system able to compute the co…
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…