FTA: â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â
Nice example of how weird large-dimensional space is. Apparently, when smart minds were asked to put as many 100-dimensional oranges in a 100-dimensional crate as they could, so far, the best they managed to do was fill less than 1% of its space with oranges, and decades of searching couldnât find a spot to put another one.
Sure Klartag isnt a sphere packing specialist by training, but he's one of the best problem solvers around. He just resolved the Hyperplane Conjecture earlier this year and has contributed to progress on related problems in convexity theory such as: KLS Conjecture, Mahler Conjecture, Central Limit Theorem for Convex Bodies, to name a few. His student Eldan's work on Stochastic Localization has also proven critical in log-concave sampling algorithms (related to the KLS conjecture, and he gave a talk at the ICM).
Also, the toolkit one uses in convex geometry, especially some of the harmonic analysis tools are quite handy in the study of sphere packing.
So "unexpected"? Not quite.
Neat. I spent a month trying to use sphere packing approaches for a better compression algorithm (I had a large amount of vectors, they were grouped through clustering). Turned out that theoretical approaches only really work for uniform data and not any sort of real-world data.
EDIT: groped -> grouped
I feel like mathematicians should be able to do a second doctorate level degree a few years after their first PhD, that must be in a adjacent field of their own, but not the same.
> 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?
> Klartag is convinced that this makes them extremely powerful: Convex shapes, he argues, are underappreciated mathematical tools.
I agree with this and I'm not even a mathematician, I've seen convex hull algorithms pop up in unexpected places to solve problems I would never have thought of using convex hull algorithms for, like a paper on automatic palette decomposition of images.
https://www.rose-hulman.edu/class/cs/csse451/Papers/DILvGRB....
Noob question: Is the optimal sphere packing correlated with a regular lattice? I.e. that's the case for 2D,3D right? If so does this extend to ND?
Don't Shannon's channel coding theorem and rate-distortion theorem establish bounds on possible sphere packing?
This should have practical applications for cow packing in physics.
does anyone know at what lowest dimension does this construction beats known best packing?
> The answer matters for potential applications to cryptography and communications
Someone can take this challenge to provide a more secure and reliable communication systems hopefully with more energy efficiency, very much an exciting research direction.
Very cool. Sphere packing comes up in a lot of contexts in applied problems. Looking forward to reviewing the paper.
I hated maths as a kid, now I love this stuff; pure maths for its own sake. Super impressive! It's a dream of mine to discover anything useful in the field.
It said his proof was basically by example. He proved more were possible.
Earlier today there was an article about neanderthal's rendering fat.
The comments pointed out that anthropologist did not know that boiling was possible before the invention of pottery. Another comment pointed out that science teachers knew that it was possible because that was something they would do in class.
Final comment was about how people ReDiscover things in different fields - - like the trapezoidal rule for integration being discovered by someone studying glucose.
This is just yet another example of how bringing expertise from a different area can help.
Canât you just montecarlo the hell out of this thing?
Why does this seem incredibly obvious to me?
Joey Chestnut?
I wonder; is this essentially why LLM tech is useful for certain Fields-medal level problems? i.e. because the LLM search construct has no barrier between sub-fields; nor between distant ones? Only multiple likely paths?
In context of packing problem, it's a bit meta to me...
An LLM contains a k-dimensional packing of known knowledge. This packing is highly inefficient because it has holes and unbridged dimensions. By injecting random seed (prompts) into the LLM probability space, it gets perturbed. Sometimes this perturbation fills a hole in the packing and/or connects two adjacent units in way nobody thought of before because it wasn't fashionable any more, or wasn't top of mind. Thus new knowledge is created within the same k-dimensional box through a novel joining-of of existing know-how.
From the article:
> Klartag had broken open a central problem in the world of lattices and sphere packing after just a few months of study and a few weeks of proof writing. âIt feels almost unfair,â he said. But thatâs often how mathematics works: Sometimes all a sticky problem needs is a few fresh ideas, and venturing outside oneâs immediate field can be rewarding. Klartagâs familiarity with convex geometry, usually a separate area of study, turned out to be just what the problem required. âThis idea was at the top of my mind because of my work,â he said. âIt was obvious to me that this was something I could try.â
This was a very confusing article, full of filler. I couldn't stand to read the "detective story" style.
Sounds like the technique is for high-dimensional ellipsoids. It relies on putting them on a grid, shrinking, then expanding according to some rules. Evidently this can produce efficient packing arrangements.
I don't think there's any shocking result ("record") for literal sphere packing. I actually encountered this in research when dynamically constructing a codebook for an error-correcting code. The problem reduces to sphere packing in N-dim space. With less efficient, naive approaches, I was able to get results that were good enough and it didn't seem to matter for what I was doing. But it's cool that someone is working on it.
A better title would have been something like: "Shrink-and-grow technique for efficiently packing n-dimensional spheres"
I have trouble explaining to my parents how my job is a real thing. I can only imagine trying to explain âI study shapes, but only ones that donât jut inwardsâ.