Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
summary
Shows that in a smoothed model (noise whose covariance has nontrivial projection in every direction) the Banaszczyk bound improves to sqrt(log d)+sqrt(log log T) with high probability and is optimal assuming the worst‑case bound is tight. Uses block fractional colorings, bitwise rounding and LP duality and chaining to prove feasibility. Proves the usual Banaszczyk bound holds and is tight for tree prefixes, reduces arbitrary DAGs to a spanning tree with few non‑tree edges and bounds discrepancy by hereditary discrepancy times sqrt(log d)+sqrt(log T).
AI-written summary · about