4 ms·

> For a given dimension d, Klartag can pack d times the number of spheres that most previous results could manage. That is, in 100-dimensional space, his method

> For a given dimension d, Klartag can pack d times the number of spheres that most previous results could manage. That is, in 100-dimensional space, his method packs roughly 100 times as many spheres; in a million-dimensional space, it packs roughly 1 million times as many. Those numbers sound wild. For various comms systems does this mean several orders of magnitude bandwidth improvement or power reduction?

lupire 1y ago
I think not, because moving to a higher dimension is exponentially worse (density ~ n^2/2^n) than this linear improvement. So it's only helpful for naturally high dimensional objects. Digital objects do not have a natural dimension (byte length), so you can choose a small dimension. https://en.m.wikipedia.org/wiki/Sphere_packing https://en.m.wikipedia.org/wiki/Sphere_packing
- tonetegeatinst 1y ago
  The addition of a dimension can be thought of as adding another variable or "axis" in simpler terms. Due to the added variable aka axis, you have increased the size of complexity. 2d shapes packed in a 2d boundary vs 3d objects in 3d space. The difference is fitting quarters on a paper vs marbles in a perfect cube. Now imagine having to find the most optimal method of packing for objects of Nth degree in Nth constraint. For example packing object that have 256 dimensional or variables into a constraint that also is 256 of complexity. I feel as your dimension aka variable increases....the amount of information to compute grows quite quickly. We can rule out some things as non optimal or non perfect, but we can also get close to perfection via trial and error. I see this as an example of the traveling salesman issue. Do you stick with a randomly selected answer, do you go with the current most optimal solution, or do you invest time and effort into finding a new solution but you risk finding a worse solution. At the end of the day is the packing efficient gains worth the computational complexity of N dimension of N constraint given it will take an unknown amount of time to find a more efficient packing solution, and the new solution could be anywhere from 0.1% to 80% more efficient.
- yorwba 1y ago
  That density is the volume density. For most applications, you care about the density in terms of number of hyperspheres instead. The largest hypersphere that fits inside an n-dimensional unit hypercube has radius 1/2 and volume π^(n/2) (1/2)^n / Γ(n/2 + 1), https://en.wikipedia.org/wiki/Volume_of_an_n-ball#Closed_form https://en.wikipedia.org/wiki/Volume_of_an_n-ball#Closed_for... so the number of hyperspheres in a given volume scales as n^2 Γ(n/2 + 1) / π^(n/2). Of course the dominant term is the factorial growth of the Gamma function, so even without the recent improvement by Klartag, using more dimensions to encode multiple values simultaneously was already preferable.
- rini17 1y ago
  Error-correcting codes in signal processing are naturally high dimensional object, also mentioned there. Don't see any reason why this research would not be applicable, we haven't found optimal error correcting code for 100 bits yet.

lupire 1y ago

I think not, because moving to a higher dimension is exponentially worse (density ~ n^2/2^n) than this linear improvement. So it's only helpful for naturally high dimensional objects. Digital objects do not have a natural dimension (byte length), so you can choose a small dimension. https://en.m.wikipedia.org/wiki/Sphere_packing https://en.m.wikipedia.org/wiki/Sphere_packing

tonetegeatinst 1y ago
The addition of a dimension can be thought of as adding another variable or "axis" in simpler terms. Due to the added variable aka axis, you have increased the size of complexity. 2d shapes packed in a 2d boundary vs 3d objects in 3d space. The difference is fitting quarters on a paper vs marbles in a perfect cube. Now imagine having to find the most optimal method of packing for objects of Nth degree in Nth constraint. For example packing object that have 256 dimensional or variables into a constraint that also is 256 of complexity. I feel as your dimension aka variable increases....the amount of information to compute grows quite quickly. We can rule out some things as non optimal or non perfect, but we can also get close to perfection via trial and error. I see this as an example of the traveling salesman issue. Do you stick with a randomly selected answer, do you go with the current most optimal solution, or do you invest time and effort into finding a new solution but you risk finding a worse solution. At the end of the day is the packing efficient gains worth the computational complexity of N dimension of N constraint given it will take an unknown amount of time to find a more efficient packing solution, and the new solution could be anywhere from 0.1% to 80% more efficient.
yorwba 1y ago
That density is the volume density. For most applications, you care about the density in terms of number of hyperspheres instead. The largest hypersphere that fits inside an n-dimensional unit hypercube has radius 1/2 and volume π^(n/2) (1/2)^n / Γ(n/2 + 1), https://en.wikipedia.org/wiki/Volume_of_an_n-ball#Closed_form https://en.wikipedia.org/wiki/Volume_of_an_n-ball#Closed_for... so the number of hyperspheres in a given volume scales as n^2 Γ(n/2 + 1) / π^(n/2). Of course the dominant term is the factorial growth of the Gamma function, so even without the recent improvement by Klartag, using more dimensions to encode multiple values simultaneously was already preferable.
rini17 1y ago
Error-correcting codes in signal processing are naturally high dimensional object, also mentioned there. Don't see any reason why this research would not be applicable, we haven't found optimal error correcting code for 100 bits yet.