17 citations · 17 across the 2 of their papers we have counts for
3 papers
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…
Laconic schema mappings: computing core universal solutions by means of SQL queries
Balder ten Cate, Laura Chiticariu, Phokion Kolaitis +1
We present a new method for computing core universal solutions in data exchange settings specified by source-to-target dependencies, by means of SQL queries. Unlike previously know…
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva +1
Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisf…