Open AccessLower Bounds for Monotone Span Programs
Author(s) -
Amos Beimel
Publication year - 1994
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v1i46.21596
Subject(s) - monotone polygon , span (engineering) , mathematics , upper and lower bounds , quadratic equation , discrete mathematics , computation , algebraic number , function (biology) , life span , combinatorics , algorithm , mathematical analysis , gerontology , medicine , civil engineering , geometry , evolutionary biology , engineering , biology
The model of span programs is a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for contact schemes, symmetric branching programs and for formula size. Monotone span programs correspond also to linear secret-sharing schemes. We present a new technique for proving lower bounds for monotone span programs. The main result proved here yields quadratic lower bounds for the size of monotone span programs, improving on the largest previously known bounds for explicit functions. The bound is asymptotically tight for the function corresponding to a class of 4-cliques.