Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-008 | 15th January 2009 00:00

Min-Rank Conjecture for Log-Depth Circuits



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.

ISSN 1433-8092 | Imprint