2024/10/29 by Swastik Kopparty, Kopparty, Swastik, Harry Sha +1
Social Sciences · Arts and Humanities · #South Asian Studies and Conflicts #Politics and Conflicts in Afghanistan, Pakistan, and Middle East #South Asian Studies and Diaspora
paper · pdf · doi:10.48550/arxiv.2410.22040
We study the problem of partitioning the unit cube [0,1]n into c parts so that each d-dimensional axis-parallel projection has small volume. This natural combinatorial/geometric question was first studied by Kopparty and Nagargoje [KN23] as a reformulation of the problem of determining the achievable parameters for seedless multimergers -- which extract randomness from `d-where' random sources (generalizing somewhere random sources). This question is closely related to influences of variables and is about a partition analogue of Shearer's lemma. Our main result answers a question of [KN23]: for d = n-1, we show that for c even as large as 2o(n), it is possible to partition [0,1]n into c parts so that every n-1-dimensional axis-parallel projection has volume at most (1/c) ( 1 + o(1) ). Previously, this was shown by [KN23] for c up to O(√(n)). The construction of our partition is related to influences of functions, and we present a clean geometric/combinatorial conjecture about this partitioning problem that would imply the KKL theorem on influences of Boolean functions.