2024/08/25 by Dongrun Cai, Cai, Dongrun, Xue Chen +6
Computer Science · #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2408.13756
openalex publication_date 2024/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
As the most powerful tool in discrepancy theory, the partial coloring method has wide applications in many problems including the Beck-Fiala problem and Spencer's celebrated result. Currently, there are two major algorithmic methods for the partial coloring method: the first approach uses linear algebraic tools; and the second is called Gaussian measure algorithm. We explore the advantages of these two methods and show the following results for them separately. 1. Spencer conjectured that the prefix discrepancy of any A ∈ \0,1\m × n is O(√(m)). We show how to find a partial coloring with prefix discrepancy O(√(m)) and Ω(n) entries in \ ± 1\ efficiently. To the best of our knowledge, this provides the first partial coloring whose prefix discrepancy is almost optimal. However, unlike the classical discrepancy problem, there is no reduction on the number of variables n for the prefix problem. By recursively applying partial coloring, we obtain a full coloring with prefix discrepancy O(√(m) ⋅ log (O(n))/(m)). Prior to this work, the best bounds of the prefix Spencer conjecture for arbitrarily large n were 2m and O(√(m log n)). 2. Our second result extends the first linear algebraic approach to a sampling algorithm in Spencer's classical setting. On the first hand, Spencer proved that there are 1.99m good colorings with discrepancy O(√(m)). Hence a natural question is to design efficient random sampling algorithms in Spencer's setting. On the other hand, some applications of discrepancy theory, prefer a random solution instead of a fixed one. Our second result is an efficient sampling algorithm whose random output has min-entropy Ω(n) and discrepancy O(√(m)). Moreover, our technique extends the linear algebraic framework by incorporating leverage scores of randomized matrix algorithms.