Random graphs and the parity quantifier

DOI10.1145/1536414.1536510zbMath1304.03074arXiv0904.2436OpenAlexW2024548433MaRDI QIDQ5172768

Swastik Kopparty, Phokion G. Kolaitis

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0904.2436

zbMATH Keywords

first-order logiczero-one lawmodular convergenceAC0

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Related Items (1)

Degree lower bounds of tower-type for approximating formulas with parity quantifiers

This page was built for publication: Random graphs and the parity quantifier