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

We argue that the symmetries of a property being tested play a
central role in property testing. We support this assertion in the
context of algebraic functions, by examining properties of functions
mapping a vector space $\K^n$ over a field $\K$ to a subfield $\F$.
We consider $\F$-linear properties that ... more >>>

Branching programs are computation models
measuring the space of (Turing machine) computations.
Read-once branching programs (BP1s) are the
most general model where each graph-theoretical path is the computation
path for some input. Exponential lower bounds on the size of read-once
branching programs are known since a long time. Nevertheless, there ... more >>>