Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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
Arkadev Chattopadhyay, Nikhil Mande

Weights at the Bottom Matter When the Top is Heavy

Revisions: 1

Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the size of THR of MAJ circuits were shown by Razborov and Sherstov (SIAM ... more >>>

ISSN 1433-8092 | Imprint