Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SIGN RANK:
Reports tagged with sign rank:
TR14-135 | 23rd October 2014
Noga Alon, Shay Moran, Amir Yehudayoff

#### Sign rank, VC dimension and spectral gaps

Revisions: 2

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>

TR17-083 | 5th May 2017