PaperlayerView exact revision on arXiv

Source-linked AI summary

The Koml\'os Problem in Matrix-Multiplication Time

Emile Anand, Peter Chen

arXiv:2610.20995v1cs.DScs.DM

TL;DR

The Komlós problem asks whether vectors of Euclidean norm at most one can be signed with dimension-independent constant discrepancy. This paper combines a gap-free resolvent potential, randomized steps, and batch reuse of a curvature subspace to give a randomized algorithm with discrepancy below 99 in expected eO(L_in + n^ω) bit operations.

  • Problem

    The Komlós problem asks whether every matrix with column norms at most 1 admits a signing with discrepancy bounded by an absolute constant independently of both dimensions.

    Source: §1 · p. 1

  • Method

    The algorithm uses a gap-free resolvent potential, random signs with coordinate energy as a separate progress measure, and a curvature subspace reused across batches.

    Source: §1.2 · p. 3

  • Results

    Discrepancy below 99 is achieved in expected eO(L_in + n^ω) bit operations for rational inputs with column norms at most 1.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    A constant discrepancy bound can be computed in expected nearly matrix-multiplication-time bit complexity.

    Source: §1.1 · p. 2, §1.2 · p. 3

    The finite-bit analysis assumes bounds T* = n^LCT on exposures, row replacements, and inverse-column requests, and V = n^LCV on 1⊤R1.

    Source: §6 · p. 13

Abstract

from arXiv · show

We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(L_{\mathrm{in}}+n^\omega)$ bit operations, where $L_{\mathrm{in}}$ is the input encoding length and $\omega$ is the exponent of matrix multiplication. The previous fastest algorithm with a constant discrepancy bound, due to Li, is deterministic and uses $O(mn+n^{\omega+2}\log^3 n)$ 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 $1/n$, 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.

1 Introduction

The paper addresses the search for a dimension-independent constant signing discrepancy and presents a randomized algorithm with discrepancy below 99 in expected matrix-multiplication-time bit complexity. Its proof combines a gap-free resolvent potential with randomized steps and reuses a curvature subspace across batches.

1 Introduction

  • A constant Komlós bound would imply O(√t) imbalance in each Beck–Fiala set and O(1) error in every linear measurement when rounding variables.The Komlós question is whether an absolute constant bounds signing discrepancy independently of both matrix dimensions.Source: §1 · p. 1

1.3 Related Work

  • Earlier work established constant discrepancy and spectral signing methods, while Li’s deterministic algorithm achieved discrepancy below 99 at higher arithmetic cost.The paper also draws on prior algorithmic discrepancy walks and fast linear-algebra tools; its notation uses L = ceil(log2(2n)) and assigns different meanings to some symbols by section.Source: §1 · p. 2, §1.3 · pp. 3–4, §1.4 · p. 4

1.1 Main Result

  • The randomized algorithm returns a signing with discrepancy below 99 in expected eO(L_in + n^ω) bit operations for rational inputs with column norms at most 1.The input encoding length is L_in, and ω is the matrix-multiplication exponent.Source: §1.1 · p. 2

1.2 Proof Overview

  • A resolvent potential replaces Li’s top-eigenvalue potential, avoiding the need for an eigenvalue gap while retaining control of the Gram matrix.Its rational form remains smooth when eigenvalues repeat or cross, and it diverges as the top eigenvalue approaches the barrier.Source: §1.2 · pp. 2–3
  • The algorithm draws a fair sign after exposing each step and measures progress through coordinate energy, allowing steps sized by a certified concavity region.The walk takes eO(n) steps rather than Li’s O(n^2 log n); a curvature subspace is reused across batches, and dynamic inverse maintenance supports direction sampling within each batch.Source: §1.2 · p. 3

2 The batched signing algorithm

The algorithm adapts Li’s fractional-coloring framework with rational row weights and a resolvent potential, then finds a subspace whose concavity remains valid across a batch. It reuses that subspace in a signing walk with anchor updates, finite-precision handling, and exact verification.

2.1 The framework from Li

  • Rows with ℓ1 norm at most one are discarded, while small-mass rows are retired and their later discrepancy is treated as a small random error.After transfers and deletions, at most s/q* nonempty rows remain.Source: §2.1 · p. 5
  • A rational weight function and the resolvent potential replace Li’s exponential weights and top-eigenvalue tracking.The resolvent potential is nonincreasing under row updates.Source: §2.1 · p. 6

2.2 A subspace for an entire batch

  • At each anchor, the algorithm finds a subspace of dimension at least ⌈s/32⌉ with a curvature margin that preserves concavity throughout a trust window.The margin absorbs drift in the curvature terms, allowing one subspace computation to serve an entire batch.Source: §2.2 · pp. 6–7

2.3 Batched Spectral Signing

  • The algorithm returns a signing with discrepancy below 99 after exact verification, and each capped trial succeeds with constant probability.It rounds the input toward zero and tests the resulting signing against the rounded matrix before returning it.Source: §2.3 · p. 8
  • The batched walk reuses its anchor subspace and sampler, refreshes them at later anchors, and restarts trials when exposure or finite-precision checks fail.It forms a signing by nearest-sign rounding and returns only after exact verification.Source: §2.3 · p. 8

3 Analysis of the walk

The walk uses independent endpoint signs and clipped symmetric steps to make progress while controlling a spectral potential. Its analysis bounds query counts, batch validity, and the resulting row errors.

3.1 Progress and batch counts

  • An epoch needs more than C_T Nτ^-2L queries with probability at most n^-10.The analysis bounds full-step counts through energy growth and short-step counts through coordinate fixation.Source: §3.1 · p. 9

3.2 Concentration and final discrepancy

  • The batch Gram bound controls every coordinate and barrier gradient at once, while independent endpoint signs make the concave spectral potential a supermartingale.The same operator-norm bound also covers retired rows, which the algorithm does not examine.Source: §3 · p. 9, §3.2 · p. 10
  • With probability at least 1 − 1/100 − n^-8 − n^-6, every batch stays in its inner trust window, query-state bounds hold, and each retired row’s error is at most 1/100.The retired-row bound includes nearest-sign rounding of the final fewer than 64 coordinates.Source: §3.2 · p. 10

4 Adaptive completion sampling

Adaptive completion sampling reuses a Gaussian completion matrix, replacing rows as constraints arrive and obtaining directions through inverse-column queries. Its guarantees control conditioning and query behavior while respecting the exposed history of the stopped process.

4 Adaptive completion sampling

  • A Gaussian completion matrix supplies directions through an inverse column, while replacing rows imposes newly fixed-coordinate and self-constraints.The independent reference row orients and scales the resulting direction; the sampler keeps the same subspace for a batch.Source: §4 · pp. 10–11
  • Real constraints define the feasible space, and the exposed history excludes hidden rows and internal inverse entries when deciding whether to stop.With 2ϵs < 1, a self-normal cannot cause the first dependence, so only a coordinate insertion can stop the process.Source: §4 · pp. 10–11
  • With probability at least 1 − n^-A, the smoothed basis is valid, no real insertion is dependent, and query and intermediate matrices have polynomially bounded norms and inverse norms.Conditional estimates use only exposed history and do not condition on this high-probability event.Source: §4 · p. 11
  • The hidden rows retain a quadratic singular-value lower tail, while an independent reference row resolves their null line using a Gaussian small-ball bound.These bounds yield a polynomially bounded right inverse for the first k − 1 rows.Source: §4 · pp. 11–12

5 Dynamic matrix formula maintenance and running time

The section maintains the sampler’s inverse queries with a dynamic matrix structure and accounts for the resulting matrix and input-processing costs. Its hierarchy supports batched inverse-row requests, while implementation work is organized around anchors and sparse incidence updates.

5 Dynamic matrix formula maintenance and running time

  • The inverse-query hierarchy rebuilds at exponentially spaced operation intervals and uses nested candidate rows to answer requests between rebuilds.The top level recomputes the full inverse every Θ(N) operations.Source: §5 · p. 12
  • The augmented inverse-maintenance structure returns three unnormalized vectors with entrywise error at most ϵ, using eO(s^ω + T s^(ω−1)) arithmetic operations with exact arithmetic.Its bit-operation guarantee assumes bounded matrix and augmentation norms; the structure uses nested candidate sets for updates and queries.Source: §5 · p. 12
  • At each anchor, spectral and sampler initialization cost eO(s^ω), while weight changes are deferred to the next anchor and completion updates remain rank-one row replacements.The epoch has eO(s) dynamic operations and polylogarithmically many anchors.Source: §5 · p. 13
  • Incidence updates and verification cost eO(Lin + mn) for dense encoding, while sparse encoding is charged by its nonzero encoding length plus O(n) to write the output.Incidence-list removals take eO(nnz(Ā)) arithmetic operations per trial.Source: §5 · p. 13

6 Finite-bit Implementation and Stability

The implementation uses inverse-polynomial tolerances and dithered rounding to couple finite-precision execution to an exact reference process. With high probability the stored outputs agree, allowing the algorithm’s guarantees to transfer to the finite implementation and yielding the stated discrepancy and expected bit-complexity bounds.

6 Finite-bit Implementation and Stability

  • The implementation uses polylogarithmically many bits and gap-free approximate diagonalization at anchors, without requiring a distributional guarantee such as subgaussianity.The analysis couples the randomized finite-precision algorithm to an ideal run.Source: §6 · pp. 13–14
  • With high probability, inverse-polynomial tolerances make the finite algorithm use the same dyadic anchor bases and stored outputs as the exact reference process.Independent dithers help prevent an approximate output error from propagating into later adaptive constraints.Source: §6 · pp. 13–14
  • At anchors, approximate basis construction uses k = ⌈s/32⌉ directions, with buffered fixed-row weights accounting for constraint errors.The tolerances keep shifted barrier arguments negative, and the construction restarts if its bounded attempts are exhausted.Source: §6 · pp. 14–15
  • 98.99 < 99: on the joint good event, the affine discrepancy and numerical error give a final bound below 99.An accepted output has discrepancy below 99 even outside that event, and exact verification succeeds with probability at least 3/4.Source: §6 · p. 15
  • Independent restarts need at most 4/3 expected trials, and the algorithm uses eO(n^ω) bit operations after input preprocessing, with preprocessing and verification adding eO(Lin).Together these yield the expected bit-complexity bound.Source: §6 · p. 15

AI Disclosure and Acknowledgements

The authors disclose assistance with argument development and presentation, and acknowledge collaborators and research support.

AI Disclosure and Acknowledgements

A Row representations and discrepancy reduction

The row-update analysis verifies barrier and scale conditions used by the rounding procedure. It also bounds the potential weights and controls how transfers and scale reductions affect the row state.

A Row representations and discrepancy reduction

A.1 Final discrepancy

The final discrepancy reduction bounds row defects from deletions, retirements, and rounding. Its guarantee assumes the walk maintains nonpositive medium-row barriers and controls retirement and offset errors.

A.1 Final discrepancy

  • Proposition A.1 assumes s < 64, nonpositive barriers for nonretired medium rows, and bounded retirement, offset-only, and never-medium-row defects.Source: §A.1 · p. 19
  • Deleted coefficients contribute a total defect bounded using the non-increasing row norm, which starts at most R_max.The total absolute deleted coefficients are bounded by R_max(8 + 63), with defect at most twice that amount.Source: §A.1 · p. 19
  • No medium row survives the final update when s < 64, and a completed row has a constant representation of magnitude below H_0.Source: §A.1 · p. 19
  • Under Proposition A.1’s assumptions, the first term in the final discrepancy bound is below 31673/320.The displayed arithmetic is H_0 + 2R_max(8 + 63) < 263/5 + (291/100)(255/16) = 31673/320.Source: §A.1 · p. 19

B Curvature and stability

The curvature analysis constructs directions where the resolvent potential remains concave and shows that this property survives within a trust window. The resolvent is monotone under specified matrix changes and does not require eigenvalue separation.

B Curvature and stability

  • The potential is nonincreasing when b increases, M decreases in Loewner order or entrywise while remaining nonnegative, or coordinates are deleted with the corresponding dimension reduction.Source: B Curvature and stability · p. 19
  • The Hessian identity ∇²F_b = P − D yields concavity when the curvature comparison holds throughout the window.Midpoint concavity then bounds the expected potential after a fair-sign step by its current value.Source: B Curvature and stability · pp. 20–21
  • At the anchor, there are at least ⌈s/32⌉ nonpositive directions: any such subspace in ker H satisfies P0[h] ≤ (1 − ρ)D0[h], the inequality used by the stability argument.Source: B Curvature and stability · p. 20

C Probability bounds for the capped walk

The probability analysis controls window failures and the stopped potential across batches and epochs. It also bounds rounding and stochastic errors to support the capped walk’s discrepancy guarantee.

C Probability bounds for the capped walk

D Adaptive Gaussian sampling proofs

The adaptive Gaussian analysis establishes regularity and tail bounds for hidden rows while controlling real constraints; the matrix-formula hierarchy maintains inverses through nested Woodbury updates.

D Adaptive Gaussian sampling proofs

  • After at most b self-normal insertions, Cbϵ_s^2I ⪯ Σ ⪯ I, κ(Σ) ≤ 2, and the unit null vector has a fair orientation.The adaptive radial law also bounds the smallest singular value of X by Pr[σ_min(X) ≤ t | F] ≤ mt^2/(2a_0).Source: D Adaptive Gaussian sampling proofs · pp. 23–24
  • The radial-law proof preserves the Gaussian completion structure under row deletion, coordinate restriction, and self-normal insertion.It uses whitening and spectral-increasing weights; the square Gram map contributes a det(S)^1/2 factor.Source: D Adaptive Gaussian sampling proofs · p. 24
  • Every nonempty real constraint matrix has smallest singular value at least β = n^-C_β, so no coordinate insertion is dependent.The proof combines coordinate constraints with self-normal separation and bounds the three failure probabilities per batch.Source: D Adaptive Gaussian sampling proofs · p. 25

E Matrix formula maintenance

  • A nested rebuild hierarchy makes the parent rows needed for each child Woodbury correction available while storing only O(d) rows per level.The small correction matrix is D = I + V⊤B^-1U, with at most 2^ℓ changed columns at a level-ℓ rebuild.Source: E Matrix formula maintenance · p. 26
  • Choosing η ≤ ϵ/[8K^2(L + 1)] keeps finite-precision Woodbury updates stable with only polylogarithmic guard bits beyond log(K/ϵ).Initialization costs O(N^ω), and the cited arithmetic-operation cost is eO(log(K/ϵ)) bit operations.Source: E Matrix formula maintenance · pp. 26–27

F Finite-precision proofs

The finite-precision proofs construct a verified anchor subspace and couple the finite algorithm to a continuous-Gaussian reference, controlling rounding and transcript disagreements.

F.1 Computing the anchor subspace

  • The anchor-subspace procedure returns a dyadic basis with near-orthonormal columns and small constraint residual in expected eO(s^ω) bit operations.Verification bounds residual and orthogonality errors before a basis is accepted.Source: §F.1 · pp. 27–28
  • A real symmetric gap-free diagonalization adapts Shah’s Gaussian deflation, bounding the probability of a poorly conditioned projected Gaussian matrix.The stated bound is Pr[σ_min(B) ≤ x] ≤ Cr^3/2x.Source: §F.1 · pp. 27–28

F.2 Transcript coupling

  • The finite algorithm is compared with a continuous-Gaussian reference using shared random-bit streams and bounded approximation errors.On the successful-reference event and away from dither boundaries, both processes store the same dyadic values and make identical public decisions.Source: §F.2 · pp. 28–29
  • Approximation and rounding errors are controlled so reference success transfers to the finite algorithm with fixed precision and an operation cap.The Gaussian sampler generates digits in expected time linear in their number.Source: §F.2 · p. 29

F.3 Propagation of numerical errors

The error analysis buffers row weights and resolvent barriers across batches, then bounds potential drift and the effects of rounded directions and endpoint signs.

F.3 Propagation of numerical errors

  • A fixed buffered row weight dominates the actual weight throughout a batch, avoiding row scans while controlling the resulting matrix increment.The increment satisfies 0 ⪯ ΔM ⪯ μ_batch M and ∥ΔM∥₂ ≤ 2μ_batch.Source: §F.3 · p. 30
  • Buffered barriers keep remaining light rows below Θ, while the resolvent vector's growth is bounded by a factor of at most 8/7.Selected rows have t_i ≥ Θ/2; unselected rows have t_i < 7Θ/8 before buffering.Source: §F.3 · p. 30
  • Fair endpoint signs and bounded curvature yield a potential-drift bound of CT* (1 + V)^3ϵ across exposures and buffer costs.The analysis also bounds protected-row barriers and limits large-row drift before a row becomes medium.Source: §F.3 · p. 30
  • Rounded proposals preserve the window and energy bounds when their errors are controlled and proposals stop before violating Gram or cap limits.The stated direction-matrix bound is ∥H∥₂² ≤ 2.Source: §F.3 · p. 30

Related papers

Loading 2610.20995v1…