Vector Balancing in Polynomial Time
En palabras de los autores
We present a spectral signing algorithm solving the Koml\'os problem with a constant discrepancy in polynomial time. Given a matrix whose columns have Euclidean norm at most , the algorithm finds a vector satisfying , where is an absolute constant. By minimizing a cubic spectral potential, our spectral signing algorithm updates the fractional coloring toward Boolean signs with time complexity .
Resultado principalEl resumen no menciona limitaciones.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 20 pages, no figures