pipette
ENEnglish

The Koml\'os Problem in Matrix-Multiplication Time

Emile Anand, Peter Chen

Preprint

En palabras de los autores

We give a randomized algorithm that, for an matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below in expected bit operations, where is the input encoding length and is the exponent of matrix multiplication. The previous fastest algorithm with a constant discrepancy bound, due to Li, is deterministic and uses arithmetic operations. We build on the spectral signing framework of Guo, Fang, and Lu and of Li, which rounds a single fractional coloring while one spectral potential controls every row. Li's potential tracks a top eigenvalue, and the gap below that eigenvalue, which can be of order , limits the length of every step. We replace it with a resolvent potential that is smooth without any gap condition, and we draw step signs at random, so that the potential only needs to be concave while progress is measured separately. Our key insight is to reuse a single subspace of directions throughout a batch of steps, thereby using only one spectral computation, so that the more expensive linear algebraic operations are paid for only polylogarithmically often at each scale. Within a batch, we sample directions from a Gaussian completion matrix whose inverse we maintain under rank-one row replacements. Finally, we use a finite-precision analysis to prove stability of the algorithm and attain the bit-complexity bound.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 30 pages