{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T12:21:45Z","timestamp":1709382105852},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"5","funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0905276"],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,10]]},"abstract":"\n The classical zero-one law for first-order logic on random graphs says that for every first-order property \u03c6 in the theory of graphs and every\n p<\/jats:italic>\n \u2208 (0,1), the probability that the random graph\n G<\/jats:italic>\n (\n n<\/jats:italic>\n ,\n p<\/jats:italic>\n ) satisfies \u03c6 approaches either 0 or 1 as\n n<\/jats:italic>\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\n G<\/jats:italic>\n (\n n<\/jats:italic>\n ,\n p<\/jats:italic>\n ) satisfies the property need not converge, and for others the limit may be strictly between 0 and 1.\n <\/jats:p>\n \n In this work, we capture the limiting behavior of properties definable in first order logic augmented with the parity quantifier, FO[\u2316], over\n G<\/jats:italic>\n (\n n<\/jats:italic>\n ,\n p<\/jats:italic>\n ), thus eluding the above hurdles. Specifically, we establish the following \u201cmodular convergence law\u201d.\n <\/jats:p>\n \n For every FO[\u2316] sentence \u03c6, there are two explicitly computable rational numbers\n \n a\n 0<\/jats:sub>\n <\/jats:italic>\n ,\n \n a\n 1<\/jats:sub>\n <\/jats:italic>\n , such that for\n i<\/jats:italic>\n \u2208 {0,1}, as\n n<\/jats:italic>\n approaches infinity, the probability that the random graph\n G<\/jats:italic>\n (2\n n<\/jats:italic>\n +\n i<\/jats:italic>\n ,\n p<\/jats:italic>\n ) satisfies \u03c6 approaches\n \n a\n i<\/jats:sub>\n <\/jats:italic>\n .\n <\/jats:p>\n \n Our results also extend appropriately to FO equipped with Mod\n q<\/jats:sub>\n quantifiers for prime\n q<\/jats:italic>\n .\n <\/jats:p>\n \n 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\n G<\/jats:italic>\n (\n n<\/jats:italic>\n ,\n p<\/jats:italic>\n ): namely, the number of copies, mod 2, of a fixed number of graphs\n F<\/jats:italic>\n 1<\/jats:sub>\n , \u2026,\n F<\/jats:italic>\n \u2113<\/jats:sub>\n of bounded size in\n G<\/jats:italic>\n (\n n<\/jats:italic>\n ,\n p<\/jats:italic>\n ). We first show that every FO[\u2316] property \u03c6 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\n n<\/jats:italic>\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.\n <\/jats:p>\n \n The first step is analogous to the Razborov-Smolensky method for lower bounds for AC\n 0<\/jats:sup>\n 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[\u2316] sentence, which is something that is not known for AC\n 0<\/jats:sup>\n [\u2316].\n <\/jats:p>","DOI":"10.1145\/2528402","type":"journal-article","created":{"date-parts":[[2013,10,23]],"date-time":"2013-10-23T15:29:17Z","timestamp":1382542157000},"page":"1-34","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Random graphs and the parity quantifier"],"prefix":"10.1145","volume":"60","author":[{"given":"Phokion G.","family":"Kolaitis","sequence":"first","affiliation":[{"name":"University of California, Santa Cruz and IBM Research, Almaden"}]},{"given":"Swastik","family":"Kopparty","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2013,10,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_10"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73008"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80027-9"},{"key":"e_1_2_1_6_1","volume-title":"Random Graphs","author":"Bollobas B.","unstructured":"Bollobas , B. 1985. Random Graphs . Academic Press . Bollobas, B. 1985. Random Graphs. Academic Press."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 10th IEEE Symposium on Logic in Computer Science. 54--64","author":"Dawar A.","unstructured":"Dawar , A. and Gr\u00e4del , E . 1995. Generalized quantifiers and 0-1 laws . In Proceedings of the 10th IEEE Symposium on Logic in Computer Science. 54--64 . Dawar, A. and Gr\u00e4del, E. 1995. Generalized quantifiers and 0-1 laws. In Proceedings of the 10th IEEE Symposium on Logic in Computer Science. 54--64."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200051756"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of Logic Colloquium'81","author":"Gaifman H.","year":"1982","unstructured":"Gaifman , H. 1982 . On local and nonlocal properties . In Proceedings of Logic Colloquium'81 , J. Stern, Ed., North Holland, 105--135. Gaifman, H. 1982. On local and nonlocal properties. In Proceedings of Logic Colloquium'81, J. Stern, Ed., North Holland, 105--135."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01071084"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-001-0332-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2008.167.481"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/421173"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3870(200202)48:2<301::AID-MALQ301>3.0.CO;2-Z"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/13.2.273"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00025-X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28441"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90065-P"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63472"},{"key":"e_1_2_1_21_1","volume-title":"Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. MATHNASUSSR: Mathe. Notes Acad. Sciences USSR 41","author":"Razborov A.","unstructured":"Razborov , A. 1987. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. MATHNASUSSR: Mathe. Notes Acad. Sciences USSR 41 . Razborov, A. 1987. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. MATHNASUSSR: Mathe. Notes Acad. Sciences USSR 41."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1988-0924703-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28440"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.15"},{"key":"e_1_2_1_26_1","unstructured":"Westerst\u00e5hl D. 1994. Iterated quantifiers. In Dynamics Polarity and Quantification M. Kanazawa and C. Pi\u00f1on Eds. 173--209. Westerst\u00e5hl D. 1994. Iterated quantifiers. In Dynamics Polarity and Quantification M. Kanazawa and C. Pi\u00f1on Eds. 173--209."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2528402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T09:19:08Z","timestamp":1672391948000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2528402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["10.1145\/2528402"],"URL":"http:\/\/dx.doi.org\/10.1145\/2528402","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
