کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430373 687969 2011 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Min-rank conjecture for log-depth circuits
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Min-rank conjecture for log-depth circuits
چکیده انگلیسی

A completion of an m-by-n matrix A   with entries in {0,1,⁎}{0,1,⁎} is obtained by setting all ⁎-entries to constants 0 and 1. A system of semi-linear equations over GF2GF2 has the form Mx=f(x)Mx=f(x), where M is a completion of A   and f:n{0,1}→m{0,1}f:{0,1}n→{0,1}m is an operator, the ith coordinate of which can only depend on variables corresponding to ⁎-entries in the ith row of A  . We conjecture that no such system can have more than 2n−ϵ⋅mr(A)2n−ϵ⋅mr(A) solutions, where ϵ>0ϵ>0 is an absolute constant and mr(A)mr(A) is the smallest rank over GF2GF2 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↦Mxx↦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.


► We formulate a conjecture about the minimal rank of partial matrices.
► The conjecture implies superlinear size lower bounds for log-depth circuits.
► We prove some results supporting the conjecture.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 77, Issue 6, November 2011, Pages 1023–1038
نویسندگان
, ,