Amos Beimel, Anna Gal, Michael S. Paterson

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 ...
more >>>

Rocco Servedio

We show that the class of monotone $2^{O(\sqrt{\log n})}$-term DNF

formulae can be PAC learned in polynomial time under the uniform

distribution. This is an exponential improvement over previous

algorithms in this model, which could learn monotone

$o(\log^2 n)$-term DNF, and is the first efficient algorithm

for ...
more >>>

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>