{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:47Z","timestamp":1750220867111,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T00:00:00Z","timestamp":1556236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"\n A Boolean function in\n n<\/jats:italic>\n variables is\n weakly evasive<\/jats:italic>\n if its decision-tree complexity is \u03a9(\n n<\/jats:italic>\n ). By\n k<\/jats:italic>\n -graphs, we mean\n k<\/jats:italic>\n -uniform hypergraphs. A\n k-graph property<\/jats:italic>\n on\n v<\/jats:italic>\n vertices is a Boolean function on\n n<\/jats:italic>\n =\n \n v<\/jats:italic>\n <\/jats:sup>\n \n k<\/jats:italic>\n <\/jats:sub>\n variables corresponding to the\n k<\/jats:italic>\n -subsets of a\n v<\/jats:italic>\n -set that is invariant under the\n v<\/jats:italic>\n ! permutations of the\n v<\/jats:italic>\n -set (isomorphisms of\n k<\/jats:italic>\n -graphs).\n <\/jats:p>\n \n In 1976, Rivest and Vuillemin proved that all nonconstant monotone graph properties (\n k<\/jats:italic>\n = 2) are weakly evasive, confirming a conjecture of Aanderaa and Rosenberg in 1973. Then, in 2013, Kulkarni, Qiao, and Sun (KQS) proved the analogous result for 3-graphs. We extend these results to\n k<\/jats:italic>\n -graphs for every fixed\n k<\/jats:italic>\n . From this, we show that monotone Boolean functions invariant under the action of a large primitive group are weakly evasive.\n <\/jats:p>\n \n Although KQS employ the powerful topological approach of Kahn et al. in 1984 combined with heavy number theory, our argument is elementary and self-contained (modulo some basic group theory). Inspired by the outline of the KQS approach, we formalize the general framework of \u201corbit augmentation sequences\u201d of sets with group actions. We show that a parameter of such sequences, called the\n spacing<\/jats:italic>\n , is a lower bound on the decision-tree complexity for any nontrivial monotone property that is \u0393-invariant for all groups \u0393 involved in the orbit augmentation sequence, assuming all those groups are\n p<\/jats:italic>\n -groups. We develop operations on such sequences such as composition and direct product that will provide helpful machinery for our applications. We apply this general technique to\n k<\/jats:italic>\n -graphs via certain liftings of\n k<\/jats:italic>\n -graphs with wreath product action of\n p<\/jats:italic>\n -groups.\n <\/jats:p>","DOI":"10.1145\/3313908","type":"journal-article","created":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T17:12:14Z","timestamp":1556557934000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Monotone Properties of\n k<\/i>\n -Uniform Hypergraphs Are Weakly Evasive"],"prefix":"10.1145","volume":"11","author":[{"given":"Timothy","family":"Black","sequence":"first","affiliation":[{"name":"University of Chicago, Chicago, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,26]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"STACS 2010: 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs)","volume":"5","author":"Babai L\u00e1szl\u00f3","year":"2010"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/13.1.1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382005"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02950404"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-012-0109-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579140"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90057-X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422454"},{"volume-title":"Theory and Applications of Models of Computation","series-title":"Lecture Notes in Computer Science","author":"Kulkarni Raghav","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02565743"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Ronald L. Rivest and Jean Vuillemin. 1976\/77. On recognizing graph properties from adjacency matrices. Theoretical Computer Science 3 3 (1976\/77) 371--384. Ronald L. Rivest and Jean Vuillemin. 1976\/77. On recognizing graph properties from adjacency matrices. Theoretical Computer Science 3 3 (1976\/77) 371--384.","DOI":"10.1016\/0304-3975(76)90053-0"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Joseph J. Rotman. 1995. An Introduction to the Theory of Groups. Springer-Verlag New York NY. Joseph J. Rotman. 1995. An Introduction to the Theory of Groups. Springer-Verlag New York NY.","DOI":"10.1007\/978-1-4612-4176-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01844851"},{"key":"e_1_2_1_14_1","unstructured":"Ivan Matveevich Vinogradov. 1937. The Method of Trigonometrical Sums in the Theory of Numbers (Russian). Steklov Institute of Mathematics. Ivan Matveevich Vinogradov. 1937. The Method of Trigonometrical Sums in the Theory of Numbers (Russian). Steklov Institute of Mathematics."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217031"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313908","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:46Z","timestamp":1750202626000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,26]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3313908"],"URL":"https:\/\/doi.org\/10.1145\/3313908","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,4,26]]},"assertion":[{"value":"2017-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}