REVIEW 3 cited by
The Komlos Conjecture Holds for Vector Colorings
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
The Komlos conjecture in discrepancy theory states that for some constant K and for any m by n matrix A whose columns lie in the unit ball there exists a +/- 1 vector x such that the infinity norm of Ax is bounded above by K. This conjecture also implies the Beck-Fiala conjecture on the discrepancy of bounded degree hypergraphs. Here we prove a natural relaxation of the Komlos conjecture: if the columns of A are assigned unit real vectors rather than +/- 1 then the Komlos conjecture holds with K=1. Our result rules out the possibility of a counterexample to the conjecture based on semidefinite programming. It also opens the way to proving tighter efficient (polynomial-time computable) upper bounds for the conjecture using semidefinite programming techniques.
Forward citations
Cited by 3 Pith papers
-
The sharp SAT/UNSAT phase transition in random ellipsoid fitting
Random ellipsoid fitting in R^d has a sharp satisfiability transition at n ~ d^2/4 Gaussian points: it is feasible below and infeasible above.
-
Decoupling via Affine Spectral-Independence: Beck-Fiala and Koml\'os Bounds Beyond Banaszczyk
A new SDP-guided Brownian-rounding technique, decoupling via affine spectral-independence, proves discrepancy O(√k) for degree-k set systems with k ≥ log² n and Õ(log^{1/4} n) for unit-norm matrices.
-
Discrepancy Theory: An Algorithmic and Geometric Perspective
A graduate-level monograph that surveys modern discrepancy theory through convex geometry and algorithms, with several simplified proofs of known results.
Discussion (0). Continue with ORCID to comment.