TR09-008 Authors: Stasys Jukna, Georg Schnitger

Publication: 4th February 2009 15:55

Downloads: 1267

Keywords:

A completion of an m-by-n matrix A with entries in {0,1,*} is obtained

by setting all *-entries to constants 0 or 1. A system of semi-linear

equations over GF(2) has the form Mx=f(x), where M is a completion of

A and f:{0,1}^n --> {0,1}^m is an operator, the i-th coordinate of

which can only depend on variables corresponding to *-entries in the

i-th row of A.

We conjecture that no such system can have more than

2^{n-c\cdot mk(A)} solutions, where c>0 is an absolute constant and

mr(A) is the smallest rank over GF(2) of a completion of A. The

conjecture is related to an old problem of proving super-linear lower

bounds on the size of log-depth boolean circuits computing linear

operators x --> Mx. The conjecture is also a generalization of a

classical question about how much larger can non-linear codes be than

linear ones. We prove some special cases of the conjecture and

establish some structural properties of solution sets.