1 Matrix-resistance and log-depth circuits

If not said otherwise, by a “matrix” A we will always mean an n-by-n (0,1) matrix.

The covering number Cov(A) of A is the smallest number r such that all 1-entries of A can be covered by at most r of its (not necessarily disjoint) all-1 submatrices. A complement of A is the matrix co-A = J - A where J is the all-1 matrix.

Example: If I_n is an identity matrix (has 1’s on the diagonal and 0’s elsewhere else) then Cov(I_n) = n.

The resistance Res(A) of A is the smallest number r for which there exist r matrices A₁,...,A_r such that:

(i) A = A₁ + A₂ + ... + A_r (sum over the reals, not mod 2), and

(ii) Cov(co-A_i) ≤ r for all i.

What makes this measure non-trivial is that we want the covering number of complements co-A_i, not of the matrices A_i themselves, be small. Would we replace (ii) by “Cov(A_i) ≤ r for all i”, the resulting measure Res′(A) would be trivial: then we would have that Res′(I_n) ≥ n^1∕2 and, more general, that Res′(A) ≥ Cov(A)^1∕2.

Equivalent definition (can be shown relatively easily): Res(A) is the smallest number r for which it is possible to associate with each row/column x a sequence x = (x₁,…,x_r) of subsets x_i of {1,…,r} such that:

1. If A[x,y] = 1 then |x_i ∩ y_i| = 0 for precisely one i.

2. If A[x,y] = 0 then |x_i ∩ y_i| > 0 for all i.

Easy counting shows that matrices A with Res(A) about n^1∕2 exist!

Proof: There are at most 2 to the power of r²n distinct assignments. But we have 2 to the power of n² distinct matrices. Since no two distinct matrices can have the same assignment, r² must be at least n. Q.E.D.

We however need explicit matrices of high resistance. That such matrices must have many 1’s follows form

Any such matrix would re-solve a 30 years old problem in circuit complexity: give a super-linear lower bound for log-depth circuits (Valiant 1977). See my paper “On graph complexity” on how does it happen.

Explicit matrices A with |A|≥ n^3∕2 ones and no 2 × 2 all-1 submatrices are known. Such are, for example, point-line incidence matrices of finite projective planes PG(q,2) with n = q² + q + 1. (In fact, these matrices have more nice properties like: any s-by-t submatrix with s⋅t > n^3∕2 must have at least one 1, meaning that the corresponding bipartite graph is a good expander.) Thus, a positive answer to Problem 2 would imply such an answer for Problem 1. (See our paper “On covering graphs by complete bipartite subgraphs” with Sasha Kulikov on how this happens.)

2 Matrix-resistance and communication complexity

Say that a matrix A has small resistance if Res(A) does not exceed 2 to the power of (log log n)^c for a constant c independent of n. Otherwise, A has large resistance.

Note that here we do not need the matrix be explicitly given—a mere existence would be enough!

A positive answer would separate the second level of the communication complexity hierarchy, show that Σ₂≠Π₂, and hence resolve a more than 20 years old problem in communication complexity (Babai, Frankl, Simon 1986).

3 Min-Rank Conjecture and circuits for linear transformations

Let M be an n-by-n matrix with entries in {0,1,*}. A completion of M is a (0,1) matrix obtained by setting the stars to constants 0 and 1. The min-rank mr(M) of M is the smallest possible rank (over the reals) of a completion of M. A canonical completion of M is obtained by setting all stars to 0.

Let now F = (f₁,…,f_n) : {0,1}ⁿ →{0,1}ⁿ be a sequence of boolean functions f_i : {0,1}ⁿ →{0,1} about which we only know the following: f_i(x₁,…,x_n) can only depend on those variables x_j for which M[i,j] = *. That is, f_i does not depend on those variables on which the ith row of M specified values (0 or 1).

If true, this would imply that using non-linear gates cannot help much when computing linear transformations, at least in log-depth circuits. See our paper “Min-rank conjecture for log-depth circuits” with Georg Schnitger for details.