## Abstract

Motivated by the Komlós conjecture in combinatorial discrepancy, we study the discrepancy of random matrices with m rows and n independent columns drawn from a bounded lattice random variable. We prove that for n at least polynomial in m, with high probability the ℓ_{∞}-discrepancy is at most twice the ℓ_{∞}-covering radius of the integer span of the support of the random variable. Applying this result to random t-sparse matrices, that is, uniformly random matrices with t ones and m−t zeroes in each column, we show that the ℓ_{∞}-discrepancy is at most 2 with probability (Formula presented.) for (Formula presented.). This improves on a bound proved by Ezra and Lovett showing the same bound for n at least m^{t}.

Original language | English (US) |
---|---|

Pages (from-to) | 64-96 |

Number of pages | 33 |

Journal | Random Structures and Algorithms |

Volume | 57 |

Issue number | 1 |

DOIs | |

State | Published - Aug 1 2020 |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

## Keywords

- Fourier
- balancing
- discrepancy
- lattice
- random matrix