Lower Bounds for Approximate Sign Rank

Riju Bindua, Hamed Hatami, Hasti Karimi +1

We prove new upper and lower bounds on $\hat{I}\mu$-approximate sign-rank, a relaxation of sign-rank introduced by Chornomaz, Moran, and Waknine (STOC 2025). We show that every $m \times n…