Balancing Random Matrices and the Local Entropy of a Planted Model

To access the document, please click [PDF]

Image credits

Dall-E2. The exact prompt was “A cartoon-style illustration of the discrepancy problem in random matrices, featuring a playful and colorful grid of matrix-like blocks”.

Synopsis

We discuss recent results on the problem of balancing random matrices. The origin is from its deterministic version, one of the most important open questions in discrepancy theory. The first part is a walk through of a very recent paper (Maillard 2024), emphasizing its contribution. Then, drawing up on the final comments of the results, we analyze the geometry of solutions, i.e. how the balancing points are arranged in space. We do this through a companion model that was the main object of the analysis for the analog vector problem. For a specific design, we find that solutions are isolated, meaning that at least Ω(n) signs have to change to hop from one to the other. This suggests that starting from a solution it is polynomially hopeless to find another.