NDLI: Random graphs and the parity quantifier

Content Provider	ACM Digital Library
Author	Kolaitis, Phokion G. Kopparty, Swastik
Copyright Year	2013
Abstract	The classical zero-one law for first-order logic on random graphs says that for every first-order property ϕ in the theory of graphs and every $\textit{p}$ ∈ (0,1), the probability that the random graph $\textit{G}(\textit{n},$ $\textit{p})$ satisfies ϕ approaches either 0 or 1 as $\textit{n}$ approaches infinity. It is well known that this law fails to hold for any formalism that can express the parity quantifier: for certain properties, the probability that $\textit{G}(\textit{n},\textit{p})$ satisfies the property need not converge, and for others the limit may be strictly between 0 and 1. In this work, we capture the limiting behavior of properties definable in first order logic augmented with the parity quantifier, FO[⌖], over $\textit{G}(\textit{n},\textit{p}),$ thus eluding the above hurdles. Specifically, we establish the following “modular convergence law”. For every FO[⌖] sentence ϕ, there are two explicitly computable rational numbers $a_{0},$ $a_{1},$ such that for $\textit{i}$ ∈ {0,1}, as $\textit{n}$ approaches infinity, the probability that the random graph $\textit{G}(2\textit{n}+\textit{i},$ $\textit{p})$ satisfies ϕ approaches $a_{i}.$ Our results also extend appropriately to FO equipped with $Mod_{q}$ quantifiers for prime $\textit{q}.$ In the process of deriving this theorem, we explore a new question that may be of interest in its own right. Specifically, we study the joint distribution of the subgraph statistics modulo 2 of $\textit{G}(\textit{n},\textit{p}):$ namely, the number of copies, mod 2, of a fixed number of graphs $F_{1},$ …, $F_{ℓ}$ of bounded size in $\textit{G}(\textit{n},\textit{p}).$ We first show that every FO[⌖] property ϕ is almost surely determined by subgraph statistics modulo 2 of the above type. Next, we show that the limiting joint distribution of the subgraph statistics modulo 2 depends only on $\textit{n}$ mod 2, and we determine this limiting distribution completely. Interestingly, both these steps are based on a common technique using multivariate polynomials over finite fields and, in particular, on a new generalization of the Gowers norm. The first step is analogous to the Razborov-Smolensky method for lower bounds for $AC^{0}$ with parity gates, yet stronger in certain ways. For instance, it allows us to obtain examples of simple graph properties that are exponentially uncorrelated with every FO[⌖] sentence, which is something that is not known for $AC^{0}[⌖].$
Starting Page	1
Ending Page	34
Page Count	34
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2528402
Journal	Journal of the ACM (JACM)
Volume Number	60
Issue Number	5
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-10-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Gowers norms Random graphs Low-degree polynomials Subgraph counts Zero-one laws
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An Algorithm for Subgraph Isomorphism

Permutation Graphs and Transitive Graphs

Two-Dimensional Parity Checking

Addressable Data Graphs

Binomial-Weighted Orthogonal Polynomials

Recognizing planar perfect graphs

Concurrent zero-knowledge

Numerical Evaluation of Symmetric Polynomials

Shifting Graphs and Their Applications

Random graphs and the parity quantifier

Similar Documents

An Algorithm for Subgraph Isomorphism

Permutation Graphs and Transitive Graphs

Two-Dimensional Parity Checking

Addressable Data Graphs

Binomial-Weighted Orthogonal Polynomials

Recognizing planar perfect graphs

Concurrent zero-knowledge

Numerical Evaluation of Symmetric Polynomials

Shifting Graphs and Their Applications

Random graphs and the parity quantifier