{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T12:30:08Z","timestamp":1762432208702,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Herchel Smith Fellowship from Harvard College"},{"name":"Simons Investigator Award"},{"name":"NSF","award":["CCF 1715187"],"award-info":[{"award-number":["CCF 1715187"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"\n We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in \u211d\n \n d<\/jats:italic>\n <\/jats:sup>\n that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., 2\n \n \u2013polylog(\n d<\/jats:italic>\n )\n <\/jats:sup>\n ) fraction of the incidences, in the sense of containing a large fraction of the points and being contained in a large fraction of the hyperplanes. In other words, the point-hyperplane incidence graph for such configurations has a large complete bipartite subgraph. Alternatively, our conjecture may be interpreted linear-algebraically as follows: Any rank-\n d<\/jats:italic>\n matrix containing at most\n O<\/jats:italic>\n (1) distinct entries in each column contains a submatrix of fractional size 2\n \n \u2013polylog(\n d<\/jats:italic>\n )\n <\/jats:sup>\n , in which each column is constant. We prove that our conjecture is equivalent to the log-rank conjecture; the crucial ingredient of this proof is a reduction from bounds for parallel\n k<\/jats:italic>\n -partitions to bounds for parallel (\n k<\/jats:italic>\n -1)-partitions. We also introduce an (apparent) strengthening of the conjecture, which relaxes the requirements that the sets of hyperplanes be parallel.\n <\/jats:p>\n \n Motivated by the connections above, we revisit well-studied questions in point-hyperplane incidence geometry\n without<\/jats:italic>\n structural assumptions (i.e., the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density \u03a9 (\u03b5\n \n 2\n d<\/jats:italic>\n <\/jats:sup>\n \/\n d<\/jats:italic>\n ) in any\n d<\/jats:italic>\n -dimensional configuration with incidence density \u03b5, qualitatively matching previous results proved using sophisticated geometric techniques. We also improve an upper-bound construction of Apfelbaum and Sharir\u00a0[\n 2<\/jats:xref>\n ], yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is \u03a9 (1\/\u221a\n d<\/jats:italic>\n ). Finally, we discuss various constructions (due to others) of products of Boolean matrices which yield configurations with incidence density \u03a9 (1) and complete bipartite subgraph density 2\n \n -\u03a9 (\u221a\n d<\/jats:italic>\n )\n <\/jats:sup>\n , and pose several questions for this special case in the alternative language of extremal set combinatorics.\n <\/jats:p>\n \n Our framework and results may help shed light on the difficulty of improving Lovett\u2019s \u00d5(\u221a rank(\n f<\/jats:italic>\n )) bound\u00a0[\n 20<\/jats:xref>\n ] for the log-rank conjecture. In particular, any improvement on this bound would imply the first complete bipartite subgraph size bounds for parallel 3-partitioned configurations which beat our generic bounds for unstructured configurations.\n <\/jats:p>","DOI":"10.1145\/3543684","type":"journal-article","created":{"date-parts":[[2022,7,26]],"date-time":"2022-07-26T11:11:39Z","timestamp":1658833899000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Point-hyperplane Incidence Geometry and the Log-rank Conjecture"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0076-521X","authenticated-orcid":false,"given":"Noah","family":"Singer","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, Massachusetts"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3718-6489","authenticated-orcid":false,"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, Massachusetts"}]}],"member":"320","published-online":{"date-parts":[[2022,9,14]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.12.008"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/050641375"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.10.001"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009350"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-06179-5"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.37236\/8253"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064098"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"issue":"2","key":"e_1_3_4_10_2","first-page":"64","article-title":"A ramsey-type theorem for bipartite graphs","volume":"10","author":"Erd\u0151s Paul","year":"2000","unstructured":"Paul Erd\u0151s, Andr\u00e1s Hajnal, and J\u00e1nos Pach. 2000. A ramsey-type theorem for bipartite graphs. Geombinatorics 10, 2 (2000), 64\u201368.","journal-title":"Geombinatorics"},{"key":"e_1_3_4_11_2","first-page":"463","article-title":"A combinatorial problem in geometry","author":"Erd\u0151s Paul","year":"1935","unstructured":"Paul Erd\u0151s and G. Szekeres. 1935. A combinatorial problem in geometry. Compositio Mathematica Tome 2 (1935), 463\u2013470.","journal-title":"Compositio Mathematica"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1515\/CRELLE.2011.157"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1007355"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-018-0046-5"},{"key":"e_1_3_4_15_2","unstructured":"Jacob Fox and Yuval Wigderson. 2021. Personal communication."},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1987-0871675-6"},{"key":"e_1_3_4_17_2","unstructured":"Alexander Golovnev Raghu Meka Madhu Sudan and Santhoshini Velusamy. 2019. Personal communication."},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9720-z"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103434634"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21924"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2724704"},{"key":"e_1_3_4_22_2","unstructured":"Shachar Lovett. 2020. The PolyTCS Project: Project 3: The Log-Rank Conjecture. Retrieved from https:\/\/polytcs.wordpress.com\/2020\/03\/23\/project-3-the-log-rank-conjecture\/."},{"key":"e_1_3_4_23_2","unstructured":"Shachar Lovett. 2021. Personal communication."},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802208"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192527"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00022-9"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2001.3184"},{"key":"e_1_3_4_28_2","unstructured":"D\u00f6m\u00f6t\u00f6r P\u00e1lv\u00f6lgyi. 2021. Personal communication."},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108671644"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970007"},{"key":"e_1_3_4_31_2","unstructured":"Noah Singer and Madhu Sudan. 2021. Point-Hyperplane Incidence Geometry and the Log-Rank Conjecture. (2021). arXiv:2101.09595v1 (first preprint version of this paper). Retrieved from https:\/\/arxiv.org\/abs\/2101.09592."},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0031-2"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543684","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543684","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543684","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:48Z","timestamp":1750186848000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543684"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3543684"],"URL":"https:\/\/doi.org\/10.1145\/3543684","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"2021-09-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-08","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}