{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T05:56:36Z","timestamp":1648878996952},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,3,6]],"date-time":"2014-03-06T00:00:00Z","timestamp":1394064000000},"content-version":"vor","delay-in-days":33,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EPSRC","award":["EP\/H026835"]},{"name":"CICYT TIN2010-20967-C04-04 (TASSAT)"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2014,2]]},"abstract":"\n Kolaitis and Kopparty have shown that for any first-order formula with parity quantifiers over the language of graphs, there is a family of multivariate polynomials of constant-degree that agree with the formula on all but a 2\n \n \u2212\u03a9(\n n<\/jats:italic>\n )\n <\/jats:sup>\n -fraction of the graphs with\n n<\/jats:italic>\n vertices. The proof bounds the degree of the polynomials by a tower of exponentials whose height is the nesting depth of parity quantifiers in the formula. We show that this tower-type dependence is necessary. We build a family of formulas of depth\n q<\/jats:italic>\n whose approximating polynomials must have degree bounded from below by a tower of exponentials of height proportional to\n q<\/jats:italic>\n . Our proof has two main parts. First, we adapt and extend the results by Kolaitis and Kopparty that describe the joint distribution of the parities of the numbers of copies of small subgraphs in a random graph to the setting of graphs of growing size. Second, we analyze a variant of Karp's graph canonical labeling algorithm and exploit its massive parallelism to get a formula of low depth that defines an almost canonical pre-order on a random graph.\n <\/jats:p>","DOI":"10.1145\/2559948","type":"journal-article","created":{"date-parts":[[2014,3,4]],"date-time":"2014-03-04T13:24:59Z","timestamp":1393939499000},"page":"1-24","source":"Crossref","is-referenced-by-count":0,"title":["Degree lower bounds of tower-type for approximating formulas with parity quantifiers"],"prefix":"10.1145","volume":"15","author":[{"given":"Albert","family":"Atserias","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}]},{"given":"Anuj","family":"Dawar","sequence":"additional","affiliation":[{"name":"University of Cambridge, Cambridge, Great Britain"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63538"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263423"},{"key":"e_1_2_1_3_1","volume-title":"0-1 laws in logic and combinatorics","author":"Compton K. J."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1804279.1804282"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200051756"},{"key":"e_1_2_1_6_1","first-page":"17","article-title":"Range and degree of realizability of formulas in the restricted predicate calculus","volume":"2","author":"Glebski\u012d Y. V.","year":"1969","journal-title":"Kibernetika"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/421173"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/034\/525336"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536510"},{"key":"e_1_2_1_10_1","volume-title":"Technical Report 33, Electronic Colloquium on Computational Complexity (ECCC).","author":"Kolaitis Ph. G.","year":"2009"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90021-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.36"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2559948","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T18:01:02Z","timestamp":1614535262000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559948"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["10.1145\/2559948"],"URL":"http:\/\/dx.doi.org\/10.1145\/2559948","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":["Computational Mathematics","Logic","General Computer Science","Theoretical Computer Science"],"published":{"date-parts":[[2014,2]]}}}