Alexander A. Sherstov

The sign-rank of a real matrix M is the least rank

of a matrix R in which every entry has the same sign as the

corresponding entry of M. We determine the sign-rank of every

matrix of the form M=[ D(|x AND y|) ]_{x,y}, where

D:{0,1,...,n}->{-1,+1} is given and ...
more >>>

Alexander Razborov, Alexander A. Sherstov

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries

is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0

for all i,j. We obtain the first exponential lower bound on the

sign-rank of a function in AC^0. Namely, let

f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}).

We show that the matrix [f(x,y)]_{x,y} has ...
more >>>

Mark Bun, Justin Thaler

The sign-rank of a matrix $A$ with entries in $\{-1, +1\}$ is the least rank of a real matrix $B$ with $A_{ij} \cdot B_{ij} > 0$ for all $i, j$. Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in AC$^0$, answering an ... more >>>