# Min-Rank Conjecture for Log-Depth Circuits - Computer Science > Computational Complexity

Abstract: A completion of an m-by-n matrix A with entries in {0,1,*} is obtained bysetting all *-entries to constants 0 or 1. A system of semi-linear equationsover GF2 has the form Mx=fx, 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 onvariables corresponding to *-entries in the i-th row of A. We conjecture thatno such system can have more than 2^{n-c\cdot mrA} solutions, where c>0 is anabsolute constant and mrA is the smallest rank over GF2 of a completion ofA. The conjecture is related to an old problem of proving super-linear lowerbounds on the size of log-depth boolean circuits computing linear operators x-> Mx. The conjecture is also a generalization of a classical question abouthow much larger can non-linear codes be than linear ones. We prove some specialcases of the conjecture and establish some structural properties of solutionsets.

Author: S. Jukna, G. Schnitger

Source: https://arxiv.org/