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 >>>

TR19-027 | 1st March 2019
Mark Bun, Nikhil Mande, Justin Thaler

Sign-Rank Can Increase Under Intersection

The communication class $UPP^{cc}$ is a communication analog of the Turing Machine complexity class $PP$. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds.

For a communication problem ... more >>>

TR19-067 | 6th May 2019
Hamed Hatami, Kaave Hosseini, Shachar Lovett

Sign rank vs Discrepancy

Revisions: 1

Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions.
In this article, we establish the strongest possible separation by constructing a Boolean matrix whose sign-rank ... more >>>

TR24-012 | 26th January 2024
Hamed Hatami, Pooya Hatami

Structure in Communication Complexity and Constant-Cost Complexity Classes

Several theorems and conjectures in communication complexity state or speculate that the complexity of a matrix in a given communication model is controlled by a related analytic or algebraic matrix parameter, e.g., rank, sign-rank, discrepancy, etc. The forward direction is typically easy as the structural implications of small complexity often ... more >>>

ISSN 1433-8092 | Imprint