Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-177 | 29th October 2024 21:49

Small Shadow Partitions

RSS-Feed




TR24-177
Authors: Swastik Kopparty, Harry Sha
Publication: 17th November 2024 16:42
Downloads: 106
Keywords: 


Abstract:

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 $2^{o(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(\sqrt{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.



ISSN 1433-8092 | Imprint