{
  "abstract": "The Komlós problem asks for signs $\\varepsilon\\in\\{-1,1\\}^n$ with $\\|A\\varepsilon\\|_\\infty$ bounded by an absolute constant whenever the columns of $A\\in\\mathbb R^{m\\times n}$ have Euclidean norm at most $1$. We give the first polynomial-time algorithm for this problem in the unit-cost real-RAM model. Our deterministic algorithm achieves discrepancy at most $8272$. As a consequence, we obtain a deterministic $O(\\sqrt t)$-discrepancy algorithm for the Beck-Fiala problem on set systems in which each element belongs to at most $t$ sets. Our algorithm rounds a fractional coloring while keeping the row sums bounded. Its key idea is to keep the number of nearly tight row constraints small relative to the number of active coordinates. We achieve this through a spectral bound based on a weighted Gram matrix of squared row entries. We maintain the bound using a cubic spectral potential and negative-curvature updates that satisfy the required linear constraints.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.23540",
  "author_total": 3,
  "authors": [
    {
      "name": "Shengtao Guo"
    },
    {
      "name": "Ethan X. Fang"
    },
    {
      "name": "Junwei Lu"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/35q4j22dc67s5.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.23540",
  "fulltext_url": null,
  "id": "35q4j22dc67s5",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.23540",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "1703|Complexity and Algorithms in Graphs"
    ]
  ],
  "openalex": "W7214027222",
  "pdf_url": "https://arxiv.org/pdf/2609.23540",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-20",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/35q4j22dc67s5.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:23:27Z",
      "native_id": "2609.23540",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.23540"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Vector Balancing in Polynomial Time",
  "title_text": "Vector Balancing in Polynomial Time",
  "type": "preprint",
  "updated_at": "2026-11-06T18:21:01Z",
  "url": "https://research.draconitic.com/paper/35q4j22dc67s5",
  "venue": "arXiv",
  "versions": []
}