# Tag Info

### Approximating the sign rank of a matrix

Recent work by Alon, Moran, and Yehudayoff gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that there exists an efficiently computable ...
Accepted

### Deterministic communication complexity vs partition number

This question has just been resolved! As I mentioned, it was known that $Pn(f) \leq D(f) \leq (Pn(f))^2$, but it was a major open problem to show that either $Pn(f) = \Theta(D(f))$ or that there ...
• 13.4k

### Research problems in communication complexity

I'll start with answers to your general questions, then give one nice open problem with applications towards circuit complexity. It's hard to say what areas a new communication complexity researcher ...
• 515
Accepted

### Nondeterministic communication complexity of set disjointness?

$N^1(DISJ_n) \geq n$. The fooling set technique actually provides lower bounds on the cover number. $C^1(f)$ is the minimum number of monochromatic rectangles needed to cover the $1$-inputs of $f$. ...
• 515

### Binary rank of binary matrix

This is equivalent to the biclique partition number of a bipartite graph. You can think of M as representing a bipartite graph $G$ on $[n] \times [m]$ in the natural way: $M_{i,j}$ is 1 if and only if ...
Accepted

### On the notion of positive rank of a matrix

There are examples of $n\times n$ real matrices of rank at most $3$ and non-negative rank at least $\sqrt{2n}$. So the non-negative rank cannot be bounded by any function of the rank in general. The ...
Accepted

### Does Rabin/Yao exist (at least in a form that can be cited)?

After more than two years, I have to assume the answer is "no". (Posting this stub answer so the question can be marked as answered.)
Accepted

### How powerful is $ACC^0$ circuit class in average case?

There seem to be typos in what you wrote; I take it you're asking: is there a function $f \in NEXP$ such that for all polynomials $p$ and infinitely many $n$, no ACC0 circuit of $p(n)$ size can ...
• 26.5k