Min-Rank Conjecture for Log-Depth Circuits
| Druh dokumentu: | Working Paper |
|---|---|
| DOI: | 10.1016/j.jcss.2009.09.003 |
| Přístupová URL adresa: | http://arxiv.org/abs/1005.1009 |
| Přírůstkové číslo: | edsarx.1005.1009 |
| Autor: | Jukna, S., Schnitger, G. |
| Rok vydání: | 2010 |
| Předmět: | |
| Zdroj: | Journal of Computer and System Sciences 77:6 (2011), 1023-1038 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.jcss.2009.09.003 |
| Popis: | 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 mr(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. Comment: 22 pages, to appear in: J. Comput.Syst.Sci. |
| Databáze: | arXiv |
| Externí odkaz: |
|