Random graphs and the parity quantifier

DOI10.1145/2528402zbMath1280.03040OpenAlexW2570749142MaRDI QIDQ5395733

Swastik Kopparty, Phokion G. Kolaitis

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2528402

zbMATH Keywords

random graphszero-one lawssubgraph countslow-degree polynomialsGowers normsparity quantifier

Mathematics Subject Classification ID

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

Related Items

Graph Decomposition and Parity, Local limit theorems for subgraph counts, Modular statistics for subgraph counts in sparse random graphs, A local central limit theorem for triangles in a random graph, Anti-concentration for subgraph counts in random graphs