Min-Rank Conjecture for Log-Depth Circuits

Details Min-Rank Conjecture for Log-Depth Circuits Min-Rank Conjecture for Log-Depth Circuits

2010-05-06

arxiv.org/abs/1005.1009v1

Journal of Computer and System Sciences 77:6 (2011), 1023-1038

Computer Science

Computational Complexity

22 pages, to appear in: J. Comput.Syst.Sci.

Scientific paper

10.1016/j.jcss.2009.09.003

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.

Affiliated with

Also associated with

No associations

Rating

Min-Rank Conjecture for Log-Depth Circuits does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Min-Rank Conjecture for Log-Depth Circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Min-Rank Conjecture for Log-Depth Circuits will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-26484